js/src/jsatom.cpp

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   2  * vim: set ts=8 sts=4 et sw=4 tw=99:
   3  * This Source Code Form is subject to the terms of the Mozilla Public
   4  * License, v. 2.0. If a copy of the MPL was not distributed with this
   5  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
   6
   7 /*
   8  * JS atom table.
   9  */
  10
  11 #include "jsatominlines.h"
  12
  13 #include "mozilla/ArrayUtils.h"
  14 #include "mozilla/RangedPtr.h"
  15
  16 #include <string.h>
  17
  18 #include "jscntxt.h"
  19 #include "jsstr.h"
  20 #include "jstypes.h"
  21
  22 #include "gc/Marking.h"
  23 #include "vm/Xdr.h"
  24
  25 #include "jscntxtinlines.h"
  26 #include "jscompartmentinlines.h"
  27 #include "jsobjinlines.h"
  28
  29 #include "vm/String-inl.h"
  30 #include "vm/Symbol-inl.h"
  31
  32 using namespace js;
  33 using namespace js::gc;
  34
  35 using mozilla::ArrayEnd;
  36 using mozilla::ArrayLength;
  37 using mozilla::RangedPtr;
  38
  39 const char*
  40 js::AtomToPrintableString(ExclusiveContext* cx, JSAtom* atom, JSAutoByteString* bytes)
  41 {
  42     JSString* str = js_QuoteString(cx, atom, 0);
  43     if (!str)
  44         return nullptr;
  45     return bytes->encodeLatin1(cx, str);
  46 }
  47
  48 #define DEFINE_PROTO_STRING(name,code,init,clasp) const char js_##name##_str[] = #name;
  49 JS_FOR_EACH_PROTOTYPE(DEFINE_PROTO_STRING)
  50 #undef DEFINE_PROTO_STRING
  51
  52 #define CONST_CHAR_STR(idpart, id, text) const char js_##idpart##_str[] = text;
  53 FOR_EACH_COMMON_PROPERTYNAME(CONST_CHAR_STR)
  54 #undef CONST_CHAR_STR
  55
  56 /* Constant strings that are not atomized. */
  57 const char js_break_str[]           = "break";
  58 const char js_case_str[]            = "case";
  59 const char js_catch_str[]           = "catch";
  60 const char js_class_str[]           = "class";
  61 const char js_const_str[]           = "const";
  62 const char js_continue_str[]        = "continue";
  63 const char js_debugger_str[]        = "debugger";
  64 const char js_default_str[]         = "default";
  65 const char js_do_str[]              = "do";
  66 const char js_else_str[]            = "else";
  67 const char js_enum_str[]            = "enum";
  68 const char js_export_str[]          = "export";
  69 const char js_extends_str[]         = "extends";
  70 const char js_finally_str[]         = "finally";
  71 const char js_for_str[]             = "for";
  72 const char js_getter_str[]          = "getter";
  73 const char js_if_str[]              = "if";
  74 const char js_implements_str[]      = "implements";
  75 const char js_import_str[]          = "import";
  76 const char js_in_str[]              = "in";
  77 const char js_instanceof_str[]      = "instanceof";
  78 const char js_interface_str[]       = "interface";
  79 const char js_new_str[]             = "new";
  80 const char js_package_str[]         = "package";
  81 const char js_private_str[]         = "private";
  82 const char js_protected_str[]       = "protected";
  83 const char js_public_str[]          = "public";
  84 const char js_send_str[]            = "send";
  85 const char js_setter_str[]          = "setter";
  86 const char js_static_str[]          = "static";
  87 const char js_super_str[]           = "super";
  88 const char js_switch_str[]          = "switch";
  89 const char js_this_str[]            = "this";
  90 const char js_try_str[]             = "try";
  91 const char js_typeof_str[]          = "typeof";
  92 const char js_void_str[]            = "void";
  93 const char js_while_str[]           = "while";
  94 const char js_with_str[]            = "with";
  95
  96 // Use a low initial capacity for atom hash tables to avoid penalizing runtimes
  97 // which create a small number of atoms.
  98 static const uint32_t JS_STRING_HASH_COUNT = 64;
  99
 100 struct CommonNameInfo
 101 {
 102     const char* str;
 103     size_t length;
 104 };
 105
 106 bool
 107 JSRuntime::initializeAtoms(JSContext* cx)
 108 {
 109     atoms_ = cx->new_<AtomSet>();
 110     if (!atoms_ || !atoms_->init(JS_STRING_HASH_COUNT))
 111         return false;
 112
 113     if (parentRuntime) {
 114         staticStrings = parentRuntime->staticStrings;
 115         commonNames = parentRuntime->commonNames;
 116         emptyString = parentRuntime->emptyString;
 117         permanentAtoms = parentRuntime->permanentAtoms;
 118         wellKnownSymbols = parentRuntime->wellKnownSymbols;
 119         return true;
 120     }
 121
 122     permanentAtoms = cx->new_<AtomSet>();
 123     if (!permanentAtoms || !permanentAtoms->init(JS_STRING_HASH_COUNT))
 124         return false;
 125
 126     staticStrings = cx->new_<StaticStrings>();
 127     if (!staticStrings || !staticStrings->init(cx))
 128         return false;
 129
 130     static const CommonNameInfo cachedNames[] = {
 131 #define COMMON_NAME_INFO(idpart, id, text) { js_##idpart##_str, sizeof(text) - 1 },
 132         FOR_EACH_COMMON_PROPERTYNAME(COMMON_NAME_INFO)
 133 #undef COMMON_NAME_INFO
 134 #define COMMON_NAME_INFO(name, code, init, clasp) { js_##name##_str, sizeof(#name) - 1 },
 135         JS_FOR_EACH_PROTOTYPE(COMMON_NAME_INFO)
 136 #undef COMMON_NAME_INFO
 137     };
 138
 139     commonNames = cx->new_<JSAtomState>();
 140     if (!commonNames)
 141         return false;
 142
 143     ImmutablePropertyNamePtr* names = reinterpret_cast<ImmutablePropertyNamePtr*>(commonNames);
 144     for (size_t i = 0; i < ArrayLength(cachedNames); i++, names++) {
 145         JSAtom* atom = Atomize(cx, cachedNames[i].str, cachedNames[i].length, InternAtom);
 146         if (!atom)
 147             return false;
 148         names->init(atom->asPropertyName());
 149     }
 150     MOZ_ASSERT(uintptr_t(names) == uintptr_t(commonNames + 1));
 151
 152     emptyString = commonNames->empty;
 153
 154     // Create the well-known symbols.
 155     wellKnownSymbols = cx->new_<WellKnownSymbols>();
 156     if (!wellKnownSymbols)
 157         return false;
 158
 159     ImmutablePropertyNamePtr* descriptions = commonNames->wellKnownSymbolDescriptions();
 160     ImmutableSymbolPtr* symbols = reinterpret_cast<ImmutableSymbolPtr*>(wellKnownSymbols);
 161     for (size_t i = 0; i < JS::WellKnownSymbolLimit; i++) {
 162         JS::Symbol* symbol = JS::Symbol::new_(cx, JS::SymbolCode(i), descriptions[i]);
 163         if (!symbol) {
 164             js_ReportOutOfMemory(cx);
 165             return false;
 166         }
 167         symbols[i].init(symbol);
 168     }
 169
 170     return true;
 171 }
 172
 173 void
 174 JSRuntime::finishAtoms()
 175 {
 176     js_delete(atoms_);
 177
 178     if (!parentRuntime) {
 179         js_delete(staticStrings);
 180         js_delete(commonNames);
 181         js_delete(permanentAtoms);
 182         js_delete(wellKnownSymbols);
 183     }
 184
 185     atoms_ = nullptr;
 186     staticStrings = nullptr;
 187     commonNames = nullptr;
 188     permanentAtoms = nullptr;
 189     wellKnownSymbols = nullptr;
 190     emptyString = nullptr;
 191 }
 192
 193 void
 194 js::MarkAtoms(JSTracer* trc)
 195 {
 196     JSRuntime* rt = trc->runtime();
 197     for (AtomSet::Enum e(rt->atoms()); !e.empty(); e.popFront()) {
 198         const AtomStateEntry& entry = e.front();
 199         if (!entry.isTagged())
 200             continue;
 201
 202         JSAtom* atom = entry.asPtr();
 203         bool tagged = entry.isTagged();
 204         MarkStringRoot(trc, &atom, "interned_atom");
 205         if (entry.asPtr() != atom)
 206             e.rekeyFront(AtomHasher::Lookup(atom), AtomStateEntry(atom, tagged));
 207     }
 208 }
 209
 210 void
 211 js::MarkPermanentAtoms(JSTracer* trc)
 212 {
 213     JSRuntime* rt = trc->runtime();
 214
 215     // Permanent atoms only need to be marked in the runtime which owns them.
 216     if (rt->parentRuntime)
 217         return;
 218
 219     // Static strings are not included in the permanent atoms table.
 220     if (rt->staticStrings)
 221         rt->staticStrings->trace(trc);
 222
 223     if (rt->permanentAtoms) {
 224         for (AtomSet::Enum e(*rt->permanentAtoms); !e.empty(); e.popFront()) {
 225             const AtomStateEntry& entry = e.front();
 226
 227             JSAtom* atom = entry.asPtr();
 228             MarkPermanentAtom(trc, atom, "permanent_table");
 229         }
 230     }
 231 }
 232
 233 void
 234 js::MarkWellKnownSymbols(JSTracer* trc)
 235 {
 236     JSRuntime* rt = trc->runtime();
 237
 238     if (rt->parentRuntime)
 239         return;
 240
 241     if (WellKnownSymbols* wks = rt->wellKnownSymbols) {
 242         for (size_t i = 0; i < JS::WellKnownSymbolLimit; i++)
 243             MarkWellKnownSymbol(trc, wks->get(i));
 244     }
 245 }
 246
 247 void
 248 JSRuntime::sweepAtoms()
 249 {
 250     if (!atoms_)
 251         return;
 252
 253     for (AtomSet::Enum e(*atoms_); !e.empty(); e.popFront()) {
 254         AtomStateEntry entry = e.front();
 255         JSAtom* atom = entry.asPtr();
 256         bool isDying = IsStringAboutToBeFinalizedFromAnyThread(&atom);
 257
 258         /* Pinned or interned key cannot be finalized. */
 259         MOZ_ASSERT_IF(hasContexts() && entry.isTagged(), !isDying);
 260
 261         if (isDying)
 262             e.removeFront();
 263     }
 264 }
 265
 266 bool
 267 JSRuntime::transformToPermanentAtoms()
 268 {
 269     MOZ_ASSERT(!parentRuntime);
 270
 271     // All static strings were created as permanent atoms, now move the contents
 272     // of the atoms table into permanentAtoms and mark each as permanent.
 273
 274     MOZ_ASSERT(permanentAtoms && permanentAtoms->empty());
 275
 276     AtomSet* temp = atoms_;
 277     atoms_ = permanentAtoms;
 278     permanentAtoms = temp;
 279
 280     for (AtomSet::Enum e(*permanentAtoms); !e.empty(); e.popFront()) {
 281         AtomStateEntry entry = e.front();
 282         JSAtom* atom = entry.asPtr();
 283         atom->morphIntoPermanentAtom();
 284     }
 285
 286     return true;
 287 }
 288
 289 bool
 290 AtomIsInterned(JSContext* cx, JSAtom* atom)
 291 {
 292     /* We treat static strings as interned because they're never collected. */
 293     if (StaticStrings::isStatic(atom))
 294         return true;
 295
 296     AtomHasher::Lookup lookup(atom);
 297
 298     /* Likewise, permanent strings are considered to be interned. */
 299     AtomSet::Ptr p = cx->permanentAtoms().readonlyThreadsafeLookup(lookup);
 300     if (p)
 301         return true;
 302
 303     AutoLockForExclusiveAccess lock(cx);
 304
 305     p = cx->runtime()->atoms().lookup(lookup);
 306     if (!p)
 307         return false;
 308
 309     return p->isTagged();
 310 }
 311
 312 /* |tbchars| must not point into an inline or short string. */
 313 template <typename CharT>
 314 MOZ_ALWAYS_INLINE
 315 static JSAtom*
 316 AtomizeAndCopyChars(ExclusiveContext* cx, const CharT* tbchars, size_t length, InternBehavior ib)
 317 {
 318     if (JSAtom* s = cx->staticStrings().lookup(tbchars, length))
 319          return s;
 320
 321     AtomHasher::Lookup lookup(tbchars, length);
 322
 323     AtomSet::Ptr pp = cx->permanentAtoms().readonlyThreadsafeLookup(lookup);
 324     if (pp)
 325         return pp->asPtr();
 326
 327     AutoLockForExclusiveAccess lock(cx);
 328
 329     AtomSet& atoms = cx->atoms();
 330     AtomSet::AddPtr p = atoms.lookupForAdd(lookup);
 331     if (p) {
 332         JSAtom* atom = p->asPtr();
 333         p->setTagged(bool(ib));
 334         return atom;
 335     }
 336
 337     AutoCompartment ac(cx, cx->atomsCompartment());
 338
 339     JSFlatString* flat = NewStringCopyN<NoGC>(cx, tbchars, length);
 340     if (!flat) {
 341         // Grudgingly forgo last-ditch GC. The alternative would be to release
 342         // the lock, manually GC here, and retry from the top. If you fix this,
 343         // please also fix or comment the similar case in Symbol::new_.
 344         js_ReportOutOfMemory(cx);
 345         return nullptr;
 346     }
 347
 348     JSAtom* atom = flat->morphAtomizedStringIntoAtom();
 349
 350     // We have held the lock since looking up p, and the operations we've done
 351     // since then can't GC; therefore the atoms table has not been modified and
 352     // p is still valid.
 353     if (!atoms.add(p, AtomStateEntry(atom, bool(ib)))) {
 354         js_ReportOutOfMemory(cx); /* SystemAllocPolicy does not report OOM. */
 355         return nullptr;
 356     }
 357
 358     return atom;
 359 }
 360
 361 template JSAtom*
 362 AtomizeAndCopyChars(ExclusiveContext* cx, const char16_t* tbchars, size_t length, InternBehavior ib);
 363
 364 template JSAtom*
 365 AtomizeAndCopyChars(ExclusiveContext* cx, const Latin1Char* tbchars, size_t length, InternBehavior ib);
 366
 367 JSAtom*
 368 js::AtomizeString(ExclusiveContext* cx, JSString* str,
 369                   js::InternBehavior ib /* = js::DoNotInternAtom */)
 370 {
 371     if (str->isAtom()) {
 372         JSAtom& atom = str->asAtom();
 373         /* N.B. static atoms are effectively always interned. */
 374         if (ib != InternAtom || js::StaticStrings::isStatic(&atom))
 375             return &atom;
 376
 377         AtomHasher::Lookup lookup(&atom);
 378
 379         /* Likewise, permanent atoms are always interned. */
 380         AtomSet::Ptr p = cx->permanentAtoms().readonlyThreadsafeLookup(lookup);
 381         if (p)
 382             return &atom;
 383
 384         AutoLockForExclusiveAccess lock(cx);
 385
 386         p = cx->atoms().lookup(lookup);
 387         MOZ_ASSERT(p); /* Non-static atom must exist in atom state set. */
 388         MOZ_ASSERT(p->asPtr() == &atom);
 389         MOZ_ASSERT(ib == InternAtom);
 390         p->setTagged(bool(ib));
 391         return &atom;
 392     }
 393
 394     JSLinearString* linear = str->ensureLinear(cx);
 395     if (!linear)
 396         return nullptr;
 397
 398     JS::AutoCheckCannotGC nogc;
 399     return linear->hasLatin1Chars()
 400            ? AtomizeAndCopyChars(cx, linear->latin1Chars(nogc), linear->length(), ib)
 401            : AtomizeAndCopyChars(cx, linear->twoByteChars(nogc), linear->length(), ib);
 402 }
 403
 404 JSAtom*
 405 js::Atomize(ExclusiveContext* cx, const char* bytes, size_t length, InternBehavior ib)
 406 {
 407     CHECK_REQUEST(cx);
 408
 409     if (!JSString::validateLength(cx, length))
 410         return nullptr;
 411
 412     const Latin1Char* chars = reinterpret_cast<const Latin1Char*>(bytes);
 413     return AtomizeAndCopyChars(cx, chars, length, ib);
 414 }
 415
 416 template <typename CharT>
 417 JSAtom*
 418 js::AtomizeChars(ExclusiveContext* cx, const CharT* chars, size_t length, InternBehavior ib)
 419 {
 420     CHECK_REQUEST(cx);
 421
 422     if (!JSString::validateLength(cx, length))
 423         return nullptr;
 424
 425     return AtomizeAndCopyChars(cx, chars, length, ib);
 426 }
 427
 428 template JSAtom*
 429 js::AtomizeChars(ExclusiveContext* cx, const Latin1Char* chars, size_t length, InternBehavior ib);
 430
 431 template JSAtom*
 432 js::AtomizeChars(ExclusiveContext* cx, const char16_t* chars, size_t length, InternBehavior ib);
 433
 434 bool
 435 js::IndexToIdSlow(ExclusiveContext* cx, uint32_t index, MutableHandleId idp)
 436 {
 437     MOZ_ASSERT(index > JSID_INT_MAX);
 438
 439     char16_t buf[UINT32_CHAR_BUFFER_LENGTH];
 440     RangedPtr<char16_t> end(ArrayEnd(buf), buf, ArrayEnd(buf));
 441     RangedPtr<char16_t> start = BackfillIndexInCharBuffer(index, end);
 442
 443     JSAtom* atom = AtomizeChars(cx, start.get(), end - start);
 444     if (!atom)
 445         return false;
 446
 447     idp.set(JSID_FROM_BITS((size_t)atom));
 448     return true;
 449 }
 450
 451 template <AllowGC allowGC>
 452 static JSAtom*
 453 ToAtomSlow(ExclusiveContext* cx, typename MaybeRooted<Value, allowGC>::HandleType arg)
 454 {
 455     MOZ_ASSERT(!arg.isString());
 456
 457     Value v = arg;
 458     if (!v.isPrimitive()) {
 459         if (!cx->shouldBeJSContext() || !allowGC)
 460             return nullptr;
 461         RootedValue v2(cx, v);
 462         if (!ToPrimitive(cx->asJSContext(), JSTYPE_STRING, &v2))
 463             return nullptr;
 464         v = v2;
 465     }
 466
 467     if (v.isString())
 468         return AtomizeString(cx, v.toString());
 469     if (v.isInt32())
 470         return Int32ToAtom(cx, v.toInt32());
 471     if (v.isDouble())
 472         return NumberToAtom(cx, v.toDouble());
 473     if (v.isBoolean())
 474         return v.toBoolean() ? cx->names().true_ : cx->names().false_;
 475     if (v.isNull())
 476         return cx->names().null;
 477     return cx->names().undefined;
 478 }
 479
 480 template <AllowGC allowGC>
 481 JSAtom*
 482 js::ToAtom(ExclusiveContext* cx, typename MaybeRooted<Value, allowGC>::HandleType v)
 483 {
 484     if (!v.isString())
 485         return ToAtomSlow<allowGC>(cx, v);
 486
 487     JSString* str = v.toString();
 488     if (str->isAtom())
 489         return &str->asAtom();
 490
 491     return AtomizeString(cx, str);
 492 }
 493
 494 template JSAtom*
 495 js::ToAtom<CanGC>(ExclusiveContext* cx, HandleValue v);
 496
 497 template JSAtom*
 498 js::ToAtom<NoGC>(ExclusiveContext* cx, Value v);
 499
 500 template<XDRMode mode>
 501 bool
 502 js::XDRAtom(XDRState<mode>* xdr, MutableHandleAtom atomp)
 503 {
 504     if (mode == XDR_ENCODE) {
 505         static_assert(JSString::MAX_LENGTH <= INT32_MAX, "String length must fit in 31 bits");
 506         uint32_t length = atomp->length();
 507         uint32_t lengthAndEncoding = (length << 1) | uint32_t(atomp->hasLatin1Chars());
 508         if (!xdr->codeUint32(&lengthAndEncoding))
 509             return false;
 510
 511         JS::AutoCheckCannotGC nogc;
 512         return atomp->hasLatin1Chars()
 513                ? xdr->codeChars(atomp->latin1Chars(nogc), length)
 514                : xdr->codeChars(const_cast<char16_t*>(atomp->twoByteChars(nogc)), length);
 515     }
 516
 517     /* Avoid JSString allocation for already existing atoms. See bug 321985. */
 518     uint32_t lengthAndEncoding;
 519     if (!xdr->codeUint32(&lengthAndEncoding))
 520         return false;
 521
 522     uint32_t length = lengthAndEncoding >> 1;
 523     bool latin1 = lengthAndEncoding & 0x1;
 524
 525     JSContext* cx = xdr->cx();
 526     JSAtom* atom;
 527     if (latin1) {
 528         const Latin1Char* chars = reinterpret_cast<const Latin1Char*>(xdr->buf.read(length));
 529         atom = AtomizeChars(cx, chars, length);
 530     } else {
 531 #if IS_LITTLE_ENDIAN
 532         /* Directly access the little endian chars in the XDR buffer. */
 533         const char16_t* chars = reinterpret_cast<const char16_t*>(xdr->buf.read(length * sizeof(char16_t)));
 534         atom = AtomizeChars(cx, chars, length);
 535 #else
 536         /*
 537          * We must copy chars to a temporary buffer to convert between little and
 538          * big endian data.
 539          */
 540         char16_t* chars;
 541         char16_t stackChars[256];
 542         if (length <= ArrayLength(stackChars)) {
 543             chars = stackChars;
 544         } else {
 545             /*
 546              * This is very uncommon. Don't use the tempLifoAlloc arena for this as
 547              * most allocations here will be bigger than tempLifoAlloc's default
 548              * chunk size.
 549              */
 550             chars = cx->runtime()->pod_malloc<char16_t>(length);
 551             if (!chars)
 552                 return false;
 553         }
 554
 555         JS_ALWAYS_TRUE(xdr->codeChars(chars, length));
 556         atom = AtomizeChars(cx, chars, length);
 557         if (chars != stackChars)
 558             js_free(chars);
 559 #endif /* !IS_LITTLE_ENDIAN */
 560     }
 561
 562     if (!atom)
 563         return false;
 564     atomp.set(atom);
 565     return true;
 566 }
 567
 568 template bool
 569 js::XDRAtom(XDRState<XDR_ENCODE>* xdr, MutableHandleAtom atomp);
 570
 571 template bool
 572 js::XDRAtom(XDRState<XDR_DECODE>* xdr, MutableHandleAtom atomp);
 573