text: /*
   * Copyright (c) Meta Platforms, Inc. and affiliates.
   *
   * This source code is licensed under the MIT license found in the
   * LICENSE file in the root directory of this source tree.
   */
  
  #define DEBUG_TYPE "identtable"
  #include "hermes/VM/IdentifierTable.h"
  
  #include "hermes/Support/UTF8.h"
  #include "hermes/VM/CallResult.h"
  #include "hermes/VM/StringBuilder.h"
  #include "hermes/VM/StringPrimitive.h"
  #include "hermes/VM/StringView.h"
  
  #include "llvh/Support/Debug.h"
  
  namespace hermes {
  namespace vm {
  
  IdentifierTable::LookupEntry::LookupEntry(
      StringPrimitive *str,
      bool isNotUniqued)
      : strPrim_(str),
        isUTF16_(false),
        isNotUniqued_(isNotUniqued),
        num_(NON_LAZY_STRING_PRIM_TAG) {
    assert(str && "Invalid string primitive pointer");
    llvh::SmallVector<char16_t, 32> storage{};
    str->appendUTF16String(storage);
    hash_ = hermes::hashString(llvh::ArrayRef<char16_t>(storage));
  }
  
  IdentifierTable::IdentifierTable() {
    hashTable_.setIdentifierTable(this);
  }
  
  CallResult<Handle<SymbolID>> IdentifierTable::getSymbolHandle(
      Runtime &runtime,
      UTF16Ref str,
      uint32_t hash) {
    auto cr = getOrCreateIdentifier(
        runtime, str, Runtime::makeNullHandle<StringPrimitive>(), hash);
    if (LLVM_UNLIKELY(cr == ExecutionStatus::EXCEPTION))
      return ExecutionStatus::EXCEPTION;
    return runtime.makeHandle(*cr);
  }
  
  CallResult<Handle<SymbolID>> IdentifierTable::getSymbolHandle(
      Runtime &runtime,
      ASCIIRef str,
      uint32_t hash) {
    auto cr = getOrCreateIdentifier(
        runtime, str, Runtime::makeNullHandle<StringPrimitive>(), hash);
    if (LLVM_UNLIKELY(cr == ExecutionStatus::EXCEPTION))
      return ExecutionStatus::EXCEPTION;
    return runtime.makeHandle(*cr);
  }
  
  SymbolID IdentifierTable::registerLazyIdentifier(ASCIIRef str) {
    return registerLazyIdentifierImpl(str, hermes::hashString(str));
  }
  
  SymbolID IdentifierTable::registerLazyIdentifier(ASCIIRef str, uint32_t hash) {
    return registerLazyIdentifierImpl(str, hash);
  }
  
  SymbolID IdentifierTable::registerLazyIdentifier(UTF16Ref str) {
    return registerLazyIdentifierImpl(str, hermes::hashString(str));
  }
  
  SymbolID IdentifierTable::registerLazyIdentifier(UTF16Ref str, uint32_t hash) {
    return registerLazyIdentifierImpl(str, hash);
  }
  
  CallResult<Handle<SymbolID>> IdentifierTable::getSymbolHandleFromPrimitive(
      Runtime &runtime,
      PseudoHandle<StringPrimitive> str) {
    assert(str && "null string primitive");
    if (str->isUniqued()) {
      // If the string was already uniqued, we can return directly.
      SymbolID id = str->getUniqueID();
      symbolReadBarrier(id.unsafeGetIndex());
      return runtime.makeHandle(id);
    }
    auto handle = runtime.makeHandle(std::move(str));
    // Force the string primitive to flatten if it's a rope.
    handle = StringPrimitive::ensureFlat(runtime, handle);
    auto cr = handle->isASCII()
        ? getOrCreateIdentifier(runtime, handle->castToASCIIRef(), handle)
        : getOrCreateIdentifier(runtime, handle->castToUTF16Ref(), handle);
    if (LLVM_UNLIKELY(cr == ExecutionStatus::EXCEPTION))
      return ExecutionStatus::EXCEPTION;
    return runtime.makeHandle(*cr);
  }
  
  StringPrimitive *IdentifierTable::getStringPrim(Runtime &runtime, SymbolID id) {
    auto &entry = getLookupTableEntry(id);
    if (entry.isStringPrim()) {
      return entry.getStringPrimRef();
    }
  
    // This is a lazy identifier, since a string primitive is requested, we must
    // materialize it.
    return materializeLazyIdentifier(runtime, id);
  }
  
  StringView IdentifierTable::getStringView(Runtime &runtime, SymbolID id) const {
    auto &entry = getLookupTableEntry(id);
    if (entry.isStringPrim()) {
      // The const_cast is a mechanical requirement as it's not worth it to
      // add const version constructors for Handle.
      Handle<StringPrimitive> handle{
          runtime, const_cast<StringPrimitive *>(entry.getStringPrim())};
      // We know that this string already exists in the identifier table,
      // and hence it's safe to call the const version of getStringView.
      return StringPrimitive::createStringViewMustBeFlat(handle);
    }
    if (entry.isLazyASCII()) {
      return StringView(entry.getLazyASCIIRef());
    }
    return StringView(entry.getLazyUTF16Ref());
  }
  
  StringView IdentifierTable::getStringViewForDev(Runtime &runtime, SymbolID id)
      const {
    if (id == SymbolID::empty()) {
      assert(false && "getStringViewForDev on empty SymbolID");
      return "<<empty>>";
    }
    if (id == SymbolID::deleted()) {
      assert(false && "getStringViewForDev on deleted SymbolID");
      return "<<deleted>>";
    }
    if (id.isInvalid()) {
      assert(false && "getStringViewForDev on invalid SymbolID");
      return "<<invalid>>";
    }
    return getStringView(runtime, id);
  }
  
  std::string IdentifierTable::convertSymbolToUTF8(SymbolID id) {
    auto &vectorEntry = getLookupTableEntry(id);
    if (vectorEntry.isStringPrim()) {
      const StringPrimitive *stringPrim = vectorEntry.getStringPrim();
      llvh::SmallVector<char16_t, 16> tmp;
      stringPrim->appendUTF16String(tmp);
      std::string out;
      convertUTF16ToUTF8WithReplacements(out, UTF16Ref{tmp});
      return out;
    } else if (vectorEntry.isLazyASCII()) {
      auto asciiRef = vectorEntry.getLazyASCIIRef();
      return std::string{asciiRef.begin(), asciiRef.end()};
    } else if (vectorEntry.isLazyUTF16()) {
      auto ref = vectorEntry.getLazyUTF16Ref();
      std::string out;
      convertUTF16ToUTF8WithReplacements(out, ref);
      return out;
    } else {
      llvm_unreachable("Invalid symbol given");
    }
    // To avoid compiler warnings.
    return "";
  }
  
  void IdentifierTable::markIdentifiers(RootAcceptor &acceptor, GC *gc) {
    for (auto &vectorEntry : lookupVector_) {
      if (!vectorEntry.isFreeSlot() && vectorEntry.isStringPrim()) {
        assert(
            !gc->inYoungGen(vectorEntry.getStringPrimRef()) &&
            "Identifiers must be allocated in the old gen");
        acceptor.acceptPtr(vectorEntry.getStringPrimRef());
      }
    }
  }
  
  void IdentifierTable::snapshotAddNodes(HeapSnapshot &snap) {
    snap.beginNode();
    snap.endNode(
        HeapSnapshot::NodeType::Native,
        "std::vector<LookupEntry>",
        GCBase::IDTracker::reserved(
            GCBase::IDTracker::ReservedObjectID::IdentifierTableLookupVector),
        lookupVector_.capacity() * sizeof(LookupEntry),
        0);
  
    snap.beginNode();
    snap.endNode(
        HeapSnapshot::NodeType::Native,
        "CompactArray",
        GCBase::IDTracker::reserved(
            GCBase::IDTracker::ReservedObjectID::IdentifierTableHashTable),
        hashTable_.additionalMemorySize(),
        0);
  
    snap.beginNode();
    snap.endNode(
        HeapSnapshot::NodeType::Native,
        "BitVector",
        GCBase::IDTracker::reserved(
            GCBase::IDTracker::ReservedObjectID::IdentifierTableMarkedSymbols),
        markedSymbols_.getMemorySize(),
        0);
  }
  
  void IdentifierTable::snapshotAddEdges(HeapSnapshot &snap) {
    snap.addNamedEdge(
        HeapSnapshot::EdgeType::Internal,
        "lookupVector",
        GCBase::IDTracker::reserved(
            GCBase::IDTracker::ReservedObjectID::IdentifierTableLookupVector));
    snap.addNamedEdge(
        HeapSnapshot::EdgeType::Internal,
        "hashTable",
        GCBase::IDTracker::reserved(
            GCBase::IDTracker::ReservedObjectID::IdentifierTableHashTable));
    snap.addNamedEdge(
        HeapSnapshot::EdgeType::Internal,
        "markedSymbols",
        GCBase::IDTracker::reserved(
            GCBase::IDTracker::ReservedObjectID::IdentifierTableMarkedSymbols));
  }
  
  void IdentifierTable::visitIdentifiers(
      const std::function<void(SymbolID, const StringPrimitive *)> &acceptor) {
    for (uint32_t i = 0; i < getSymbolsEnd(); ++i) {
      auto &vectorEntry = getLookupTableEntry(i);
      if (!vectorEntry.isFreeSlot()) {
        const StringPrimitive *str =
            vectorEntry.isStringPrim() ? vectorEntry.getStringPrim() : nullptr;
        acceptor(SymbolID::unsafeCreate(i), str);
      }
    }
  }
  
  template <typename T, bool Unique>
  CallResult<PseudoHandle<StringPrimitive>>
  IdentifierTable::allocateDynamicString(
      Runtime &runtime,
      llvh::ArrayRef<T> str,
      Handle<StringPrimitive> primHandle) {
    size_t length = str.size();
  
    assert(
        (!primHandle || primHandle->isFlat()) && "StringPrimitive must be flat");
  
    GCScope gcScope(runtime);
  
    PseudoHandle<StringPrimitive> result;
    if (StringPrimitive::isExternalLength(length)) {
      if (LLVM_UNLIKELY(length > StringPrimitive::MAX_STRING_LENGTH)) {
        return runtime.raiseRangeError("String length exceeds limit");
      }
      std::basic_string<T> stdString(str.begin(), str.end());
      auto cr = ExternalStringPrimitive<T>::createLongLived(
          runtime, std::move(stdString));
      if (LLVM_UNLIKELY(cr == ExecutionStatus::EXCEPTION)) {
        return ExecutionStatus::EXCEPTION;
      }
      result = createPseudoHandle(vmcast<StringPrimitive>(*cr));
    } else {
      auto *tmp = runtime.makeAVariable<
          DynamicStringPrimitive<T, Unique>,
          HasFinalizer::No,
          LongLived::Yes>(
          DynamicStringPrimitive<T, Unique>::allocationSize((uint32_t)length),
          length);
      // Since we keep a raw pointer to mem, no more JS heap allocations after
      // this point.
      NoAllocScope _(runtime);
      if (primHandle) {
        str = primHandle->getStringRef<T>();
      }
      std::copy(str.begin(), str.end(), tmp->getRawPointerForWrite());
      result = createPseudoHandle<StringPrimitive>(tmp);
    }
  
    return result;
  }
  
  void IdentifierTable::symbolReadBarrier(uint32_t id) {
    // Set the mark bool inside the symbol table entry so that this symbol isn't
    // garbage collected.
    // The reason this exists is that a Symbol can be retrieved via a string hash
    // that doesn't otherwise keep the symbol alive while in the middle of a GC.
    markedSymbols_.set(id);
  }
  
  uint32_t IdentifierTable::allocIDAndInsert(
      uint32_t hashTableIndex,
      StringPrimitive *strPrim) {
    uint32_t nextId = allocNextID();
    SymbolID symbolId = SymbolID::unsafeCreate(nextId);
    assert(lookupVector_[nextId].isFreeSlot() && "Allocated a non-free slot");
    strPrim->convertToUniqued(symbolId);
  
    // We must assign strPrim to the lookupVector before inserting to
    // hashTable_, because inserting to hashTable_ could trigger a grow/rehash,
    // which requires accessing the newly inserted string primitive.
    new (&lookupVector_[nextId]) LookupEntry(strPrim);
  
    hashTable_.insert(hashTableIndex, symbolId);
  
    LLVM_DEBUG(
        llvh::dbgs() << "allocated symbol " << nextId << " '" << strPrim
                     << "'\n");
  
    return nextId;
  }
  
  template <typename T>
  CallResult<SymbolID> IdentifierTable::getOrCreateIdentifier(
      Runtime &runtime,
      llvh::ArrayRef<T> str,
      Handle<StringPrimitive> maybeIncomingPrimHandle,
      uint32_t hash) {
    assert(
        !(maybeIncomingPrimHandle && maybeIncomingPrimHandle->isUniqued()) &&
        "Should not call getOrCreateIdentifier with a uniqued StrPrim");
    assert(
        (!maybeIncomingPrimHandle || maybeIncomingPrimHandle->isFlat()) &&
        "StringPrimitive must be flat");
  
    auto idx = hashTable_.lookupString(str, hash);
    if (hashTable_.isValid(idx)) {
      NoAllocScope scope{runtime};
      const auto id = hashTable_.get(idx);
      // Read barrier here because a symbol value is getting read out of the hash
      // map.
      symbolReadBarrier(id);
      return SymbolID::unsafeCreate(id);
    }
  
    // It is tempting here to check whether the incoming StringPrimitive can be
    // uniqued, and use it instead of allocating a new one. The problem is that
    // identifiers must always be allocated in "long-lived" memory, but we don't
    // (yet) have a way of checking whether that is the case. If in the future we
    // did get that GC API, the check would look something like this:
    // \code
    // if (maybeIncomingPrimHandle &&
    //     LLVM_UNLIKELY(maybeIncomingPrimHandle->canBeUniqued()) &&
    //     runtime.getHeap().isLongLived(*maybeIncomingPrimHandle)) {
    //   return SymbolID::unsafeCreate(
    //       allocIDAndInsert(idx, maybeIncomingPrimHandle.get()));
    // }
    // \endcode
  
    CallResult<PseudoHandle<StringPrimitive>> cr =
        allocateDynamicString(runtime, str, maybeIncomingPrimHandle);
    if (cr == ExecutionStatus::EXCEPTION) {
      return ExecutionStatus::EXCEPTION;
    }
  
    // Allocate the id after we have performed memory allocations because a GC
    // would have freed id.
    return SymbolID::unsafeCreate(allocIDAndInsert(idx, cr->get()));
  }
  
  StringPrimitive *IdentifierTable::getExistingStringPrimitiveOrNull(
      Runtime &runtime,
      llvh::ArrayRef<char16_t> str) {
    auto idx = hashTable_.lookupString(str, hashString(str));
    if (!hashTable_.isValid(idx)) {
      return nullptr;
    }
    // Use a handle since getStringPrim may need to materialize the string.
    const auto id = hashTable_.get(idx);
    symbolReadBarrier(id);
    Handle<SymbolID> sym(runtime, SymbolID::unsafeCreate(id));
    return getStringPrim(runtime, *sym);
  }
  
  template <typename T>
  SymbolID IdentifierTable::registerLazyIdentifierImpl(
      llvh::ArrayRef<T> str,
      uint32_t hash) {
    auto idx = hashTable_.lookupString(str, hash);
    if (hashTable_.isValid(idx)) {
      // If the string is already in the table, return it.
      const auto id = hashTable_.get(idx);
      symbolReadBarrier(id);
      return SymbolID::unsafeCreate(id);
    }
    uint32_t nextId = allocNextID();
    SymbolID symbolId = SymbolID::unsafeCreate(nextId);
    assert(lookupVector_[nextId].isFreeSlot() && "Allocated a non-free slot");
    new (&lookupVector_[nextId]) LookupEntry(str, hash);
    hashTable_.insert(idx, symbolId);
    LLVM_DEBUG(
        llvh::dbgs() << "Allocated lazy identifier: " << nextId << " " << str
                     << "\n");
    return symbolId;
  }
  
  StringPrimitive *IdentifierTable::materializeLazyIdentifier(
      Runtime &runtime,
      SymbolID id) {
    auto &entry = getLookupTableEntry(id);
    assert(
        (entry.isLazyASCII() || entry.isLazyUTF16()) && "identifier is not lazy");
    // This in theory can throw if running out of memory. However there are only
    // finite number of persistent identifiers, and we should always have enough
    // memory to hold them.
    PseudoHandle<StringPrimitive> strPrim = runtime.ignoreAllocationFailure(
        entry.isLazyASCII() ? allocateDynamicString(
                                  runtime,
                                  entry.getLazyASCIIRef(),
                                  Runtime::makeNullHandle<StringPrimitive>())
                            : allocateDynamicString(
                                  runtime,
                                  entry.getLazyUTF16Ref(),
                                  Runtime::makeNullHandle<StringPrimitive>()));
    if (id.isUniqued())
      strPrim->convertToUniqued(id);
    LLVM_DEBUG(llvh::dbgs() << "Materializing lazy identifier " << id << "\n");
    entry.materialize(strPrim.get());
    return strPrim.get();
  }
  
  void IdentifierTable::freeSymbol(uint32_t index) {
    assert(index < lookupVector_.size() && "Invalid symbol index to free");
    assert(
        lookupVector_[index].isNonLazyStringPrim() &&
        "The specified symbol cannot be freed");
  
    LLVM_DEBUG(
        llvh::dbgs() << "Freeing symbol index " << index << " '"
                     << lookupVector_[index].getStringPrim() << "'\n");
  
    if (LLVM_LIKELY(!lookupVector_[index].isNotUniqued())) {
      auto *strPrim =
          const_cast<StringPrimitive *>(lookupVector_[index].getStringPrim());
      strPrim->clearUniquedBit();
      hashTable_.remove(strPrim);
    }
    freeID(index);
  }
  
  uint32_t IdentifierTable::allocNextID() {
    // If the free list is empty, grow the array.
    if (firstFreeID_ == LookupEntry::FREE_LIST_END) {
      uint32_t newID = lookupVector_.size();
      if (LLVM_UNLIKELY(newID > LookupEntry::MAX_IDENTIFIER)) {
        hermes_fatal("Failed to allocate Identifier: IdentifierTable is full");
      }
      lookupVector_.emplace_back();
      markedSymbols_.push_back(true);
      LLVM_DEBUG(
          llvh::dbgs() << "Allocated new symbol id at end " << newID << "\n");
      // Don't need to tell the GC about this ID, it will assume any growth is
      // live.
      return newID;
    }
  
    // Allocate from the free list.
    uint32_t nextId = firstFreeID_;
    auto &entry = getLookupTableEntry(nextId);
    assert(entry.isFreeSlot() && "firstFreeID_ is not a free slot");
    firstFreeID_ = entry.getNextFreeSlot();
    markedSymbols_.set(nextId);
    LLVM_DEBUG(llvh::dbgs() << "Allocated freed symbol id " << nextId << "\n");
    return nextId;
  }
  
  void IdentifierTable::freeID(uint32_t id) {
    assert(
        lookupVector_[id].isStringPrim() &&
        "The specified symbol cannot be freed");
  
    // Add the freed index to the free list.
    lookupVector_[id].free(firstFreeID_);
    firstFreeID_ = id;
    LLVM_DEBUG(llvh::dbgs() << "Freeing ID " << id << "\n");
  }
  
  void IdentifierTable::unmarkSymbols() {
    markedSymbols_.reset();
  }
  
  void IdentifierTable::freeUnmarkedSymbols(
      const llvh::BitVector &markedSymbols,
      GC::IDTracker &tracker) {
    assert(
        markedSymbols.size() <= lookupVector_.size() &&
        "Size of markedSymbols must be less than the current lookupVector");
    assert(
        markedSymbols_.size() == lookupVector_.size() &&
        "Size of markedSymbols_ must be the same as the lookupVector");
    markedSymbols_ |= markedSymbols;
    // Flip and find set bits, which will correspond to symbols that weren't
    // marked.
    markedSymbols_.flip();
    const bool isTrackingIDs = tracker.isTrackingIDs();
    const uint32_t markedSymbolsSize = markedSymbols.size();
    for (const uint32_t i : markedSymbols_.set_bits()) {
      // Don't check any bits after the passed-in bits, which represent the number
      // of symbols alive at the start of the collection.
      if (i >= markedSymbolsSize) {
        break;
      }
      // We never free StringPrimitives that are materialized from a lazy
      // identifier.
      if (lookupVector_[i].isNonLazyStringPrim()) {
        if (isTrackingIDs) {
          tracker.untrackSymbol(i);
        }
        freeSymbol(i);
      }
    }
    markedSymbols_.reset();
  }
  
  #ifdef HERMES_SLOW_DEBUG
  bool IdentifierTable::isSymbolLive(SymbolID id) const {
    auto &entry = getLookupTableEntry(id);
    // If the entry is not a free slot, then it is live.
    return !entry.isFreeSlot();
  }
  
  const StringPrimitive *IdentifierTable::getStringForSymbol(SymbolID id) const {
    auto &entry = getLookupTableEntry(id);
    if (entry.isStringPrim()) {
      return entry.getStringPrim();
    }
    return nullptr;
  }
  #endif
  
  SymbolID IdentifierTable::createNotUniquedLazySymbol(ASCIIRef desc) {
    uint32_t nextID = allocNextID();
    new (&lookupVector_[nextID]) LookupEntry(desc, 0, true);
    return SymbolID::unsafeCreateNotUniqued(nextID);
  }
  
  CallResult<SymbolID> IdentifierTable::createNotUniquedSymbol(
      Runtime &runtime,
      Handle<StringPrimitive> desc) {
    uint32_t nextID = allocNextID();
  
    if (runtime.getHeap().inYoungGen(desc.get())) {
      // Need to reallocate in the old gen if the description is in the young gen.
      CallResult<PseudoHandle<StringPrimitive>> longLivedStr = desc->isASCII()
          ? allocateDynamicString<char, /* Unique */ false>(
                runtime, desc->castToASCIIRef(), desc)
          : allocateDynamicString<char16_t, /* Unique */ false>(
                runtime, desc->castToUTF16Ref(), desc);
      // Since we keep a raw pointer to mem, no more JS heap allocations after
      // this point.
      NoAllocScope _(runtime);
      if (LLVM_UNLIKELY(longLivedStr == ExecutionStatus::EXCEPTION)) {
        return ExecutionStatus::EXCEPTION;
      }
      new (&lookupVector_[nextID]) LookupEntry(longLivedStr->get(), true);
    } else {
      // Description is already in the old gen, just point to it.
      new (&lookupVector_[nextID]) LookupEntry(*desc, true);
    }
  
    return SymbolID::unsafeCreateNotUniqued(nextID);
  }
  
  llvh::raw_ostream &operator<<(llvh::raw_ostream &OS, SymbolID symbolID) {
    if (symbolID.isInvalid())
      return OS << "SymbolID(INVALID)";
    else if (symbolID == SymbolID::deleted())
      return OS << "SymbolID(DELETED)";
    else
      return OS << "SymbolID("
                << (symbolID.isUniqued() ? "(Uniqued)" : "(Not Uniqued)")
                << symbolID.unsafeGetIndex() << ")";
  }
  
  } // namespace vm
  } // namespace hermes
  
  #undef DEBUG_TYPE
  