js/src/vm/StaticStrings.h

   1 /* -*- Mode: C++; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   2  * vim: set ts=8 sts=2 et sw=2 tw=80:
   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 #ifndef vm_StaticStrings_h
   8 #define vm_StaticStrings_h
   9
  10 #include "mozilla/Assertions.h"
  11 #include "mozilla/Attributes.h"
  12 #include "mozilla/TextUtils.h"
  13
  14 #include <stddef.h>
  15 #include <stdint.h>
  16 #include <type_traits>
  17
  18 #include "jstypes.h"
  19
  20 #include "js/TypeDecls.h"
  21
  22 class JS_PUBLIC_API JSTracer;
  23 struct JS_PUBLIC_API JSContext;
  24
  25 class JSAtom;
  26 class JSLinearString;
  27 class JSString;
  28
  29 namespace js {
  30
  31 namespace frontend {
  32 class ParserAtomsTable;
  33 class TaggedParserAtomIndex;
  34 class WellKnownParserAtoms;
  35 struct CompilationAtomCache;
  36 }  // namespace frontend
  37
  38 class StaticStrings {
  39   // NOTE: The WellKnownParserAtoms rely on these tables and may need to be
  40   //       update if these tables are changed.
  41   friend class js::frontend::ParserAtomsTable;
  42   friend class js::frontend::TaggedParserAtomIndex;
  43   friend class js::frontend::WellKnownParserAtoms;
  44   friend struct js::frontend::CompilationAtomCache;
  45
  46  private:
  47   // Strings matches `[A-Za-z0-9$_]{2}` pattern.
  48   // Store each character in 6 bits.
  49   // See fromSmallChar/toSmallChar for the mapping.
  50   static constexpr size_t SMALL_CHAR_BITS = 6;
  51   static constexpr size_t SMALL_CHAR_MASK = js::BitMask(SMALL_CHAR_BITS);
  52
  53   // To optimize ASCII -> small char, allocate a table.
  54   static constexpr size_t SMALL_CHAR_TABLE_SIZE = 128U;
  55   static constexpr size_t NUM_SMALL_CHARS = js::Bit(SMALL_CHAR_BITS);
  56   static constexpr size_t NUM_LENGTH2_ENTRIES =
  57       NUM_SMALL_CHARS * NUM_SMALL_CHARS;
  58
  59   JSAtom* length2StaticTable[NUM_LENGTH2_ENTRIES] = {};  // zeroes
  60
  61  public:
  62   /* We keep these public for the JITs. */
  63   static const size_t UNIT_STATIC_LIMIT = 256U;
  64   JSAtom* unitStaticTable[UNIT_STATIC_LIMIT] = {};  // zeroes
  65
  66   static const size_t INT_STATIC_LIMIT = 256U;
  67   JSAtom* intStaticTable[INT_STATIC_LIMIT] = {};  // zeroes
  68
  69   StaticStrings() = default;
  70
  71   bool init(JSContext* cx);
  72   void trace(JSTracer* trc);
  73
  74   static bool hasUint(uint32_t u) { return u < INT_STATIC_LIMIT; }
  75
  76   JSAtom* getUint(uint32_t u) {
  77     MOZ_ASSERT(hasUint(u));
  78     return intStaticTable[u];
  79   }
  80
  81   static bool hasInt(int32_t i) { return uint32_t(i) < INT_STATIC_LIMIT; }
  82
  83   JSAtom* getInt(int32_t i) {
  84     MOZ_ASSERT(hasInt(i));
  85     return getUint(uint32_t(i));
  86   }
  87
  88   static bool hasUnit(char16_t c) { return c < UNIT_STATIC_LIMIT; }
  89
  90   JSAtom* getUnit(char16_t c) {
  91     MOZ_ASSERT(hasUnit(c));
  92     return unitStaticTable[c];
  93   }
  94
  95   /* May not return atom, returns null on (reported) failure. */
  96   inline JSLinearString* getUnitStringForElement(JSContext* cx, JSString* str,
  97                                                  size_t index);
  98
  99   template <typename CharT>
 100   static bool isStatic(const CharT* chars, size_t len);
 101
 102   /* Return null if no static atom exists for the given (chars, length). */
 103   template <typename CharT>
 104   MOZ_ALWAYS_INLINE JSAtom* lookup(const CharT* chars, size_t length) {
 105     static_assert(std::is_same_v<CharT, JS::Latin1Char> ||
 106                       std::is_same_v<CharT, char16_t>,
 107                   "for understandability, |chars| must be one of a few "
 108                   "identified types");
 109
 110     switch (length) {
 111       case 1: {
 112         char16_t c = chars[0];
 113         if (c < UNIT_STATIC_LIMIT) {
 114           return getUnit(c);
 115         }
 116         return nullptr;
 117       }
 118       case 2:
 119         if (fitsInSmallChar(chars[0]) && fitsInSmallChar(chars[1])) {
 120           return getLength2(chars[0], chars[1]);
 121         }
 122         return nullptr;
 123       case 3:
 124         /*
 125          * Here we know that JSString::intStringTable covers only 256 (or at
 126          * least not 1000 or more) chars. We rely on order here to resolve the
 127          * unit vs. int string/length-2 string atom identity issue by giving
 128          * priority to unit strings for "0" through "9" and length-2 strings for
 129          * "10" through "99".
 130          */
 131         int i;
 132         if (fitsInLength3Static(chars[0], chars[1], chars[2], &i)) {
 133           return getInt(i);
 134         }
 135         return nullptr;
 136     }
 137
 138     return nullptr;
 139   }
 140
 141   MOZ_ALWAYS_INLINE JSAtom* lookup(const char* chars, size_t length) {
 142     // Collapse calls for |const char*| into |const Latin1Char char*| to avoid
 143     // excess instantiations.
 144     return lookup(reinterpret_cast<const JS::Latin1Char*>(chars), length);
 145   }
 146
 147  private:
 148   using SmallChar = uint8_t;
 149
 150   struct SmallCharTable {
 151     SmallChar storage[SMALL_CHAR_TABLE_SIZE];
 152
 153     constexpr SmallChar& operator[](size_t idx) { return storage[idx]; }
 154     constexpr const SmallChar& operator[](size_t idx) const {
 155       return storage[idx];
 156     }
 157   };
 158
 159   static const SmallChar INVALID_SMALL_CHAR = -1;
 160
 161   static bool fitsInSmallChar(char16_t c) {
 162     return c < SMALL_CHAR_TABLE_SIZE &&
 163            toSmallCharTable[c] != INVALID_SMALL_CHAR;
 164   }
 165
 166   template <typename CharT>
 167   static bool fitsInLength3Static(CharT c1, CharT c2, CharT c3, int* i) {
 168     static_assert(INT_STATIC_LIMIT <= 299,
 169                   "static int strings assumed below to be at most "
 170                   "three digits where the first digit is either 1 or 2");
 171     if ('1' <= c1 && c1 < '3' && '0' <= c2 && c2 <= '9' && '0' <= c3 &&
 172         c3 <= '9') {
 173       *i = (c1 - '0') * 100 + (c2 - '0') * 10 + (c3 - '0');
 174
 175       if (unsigned(*i) < INT_STATIC_LIMIT) {
 176         return true;
 177       }
 178     }
 179     return false;
 180   }
 181
 182   static constexpr JS::Latin1Char fromSmallChar(SmallChar c);
 183
 184   static constexpr SmallChar toSmallChar(uint32_t c);
 185
 186   static constexpr SmallCharTable createSmallCharTable();
 187
 188   static const SmallCharTable toSmallCharTable;
 189
 190   static constexpr JS::Latin1Char firstCharOfLength2(size_t s) {
 191     return fromSmallChar(s >> SMALL_CHAR_BITS);
 192   }
 193   static constexpr JS::Latin1Char secondCharOfLength2(size_t s) {
 194     return fromSmallChar(s & SMALL_CHAR_MASK);
 195   }
 196
 197   static constexpr JS::Latin1Char firstCharOfLength3(uint32_t i) {
 198     return '0' + (i / 100);
 199   }
 200   static constexpr JS::Latin1Char secondCharOfLength3(uint32_t i) {
 201     return '0' + ((i / 10) % 10);
 202   }
 203   static constexpr JS::Latin1Char thirdCharOfLength3(uint32_t i) {
 204     return '0' + (i % 10);
 205   }
 206
 207   static MOZ_ALWAYS_INLINE size_t getLength2Index(char16_t c1, char16_t c2) {
 208     MOZ_ASSERT(fitsInSmallChar(c1));
 209     MOZ_ASSERT(fitsInSmallChar(c2));
 210     return (size_t(toSmallCharTable[c1]) << SMALL_CHAR_BITS) +
 211            toSmallCharTable[c2];
 212   }
 213
 214   // Same as getLength2Index, but withtout runtime assertion,
 215   // this should be used only for known static string.
 216   static constexpr size_t getLength2IndexStatic(char c1, char c2) {
 217     return (size_t(toSmallChar(c1)) << SMALL_CHAR_BITS) + toSmallChar(c2);
 218   }
 219
 220   MOZ_ALWAYS_INLINE JSAtom* getLength2FromIndex(size_t index) {
 221     return length2StaticTable[index];
 222   }
 223
 224   MOZ_ALWAYS_INLINE JSAtom* getLength2(char16_t c1, char16_t c2) {
 225     return getLength2FromIndex(getLength2Index(c1, c2));
 226   }
 227 };
 228
 229 /*
 230  * Declare length-2 strings. We only store strings where both characters are
 231  * alphanumeric. The lower 10 short chars are the numerals, the next 26 are
 232  * the lowercase letters, and the next 26 are the uppercase letters.
 233  */
 234
 235 constexpr JS::Latin1Char StaticStrings::fromSmallChar(SmallChar c) {
 236   if (c < 10) {
 237     return c + '0';
 238   }
 239   if (c < 36) {
 240     return c + 'a' - 10;
 241   }
 242   if (c < 62) {
 243     return c + 'A' - 36;
 244   }
 245   if (c == 62) {
 246     return '$';
 247   }
 248   return '_';
 249 }
 250
 251 constexpr StaticStrings::SmallChar StaticStrings::toSmallChar(uint32_t c) {
 252   if (mozilla::IsAsciiDigit(c)) {
 253     return c - '0';
 254   }
 255   if (mozilla::IsAsciiLowercaseAlpha(c)) {
 256     return c - 'a' + 10;
 257   }
 258   if (mozilla::IsAsciiUppercaseAlpha(c)) {
 259     return c - 'A' + 36;
 260   }
 261   if (c == '$') {
 262     return 62;
 263   }
 264   if (c == '_') {
 265     return 63;
 266   }
 267   return StaticStrings::INVALID_SMALL_CHAR;
 268 }
 269
 270 }  // namespace js
 271
 272 #endif /* vm_StringType_h */