contrib/llvm-project/lldb/source/Utility/ConstString.cpp

   1 //===-- ConstString.cpp -----------------------------------------*- C++ -*-===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "lldb/Utility/ConstString.h"
  10
  11 #include "lldb/Utility/Stream.h"
  12
  13 #include "llvm/ADT/StringMap.h"
  14 #include "llvm/ADT/iterator.h"
  15 #include "llvm/Support/Allocator.h"
  16 #include "llvm/Support/DJB.h"
  17 #include "llvm/Support/FormatProviders.h"
  18 #include "llvm/Support/RWMutex.h"
  19 #include "llvm/Support/Threading.h"
  20
  21 #include <algorithm>
  22 #include <array>
  23 #include <utility>
  24
  25 #include <inttypes.h>
  26 #include <stdint.h>
  27 #include <string.h>
  28
  29 using namespace lldb_private;
  30
  31 class Pool {
  32 public:
  33   typedef const char *StringPoolValueType;
  34   typedef llvm::StringMap<StringPoolValueType, llvm::BumpPtrAllocator>
  35       StringPool;
  36   typedef llvm::StringMapEntry<StringPoolValueType> StringPoolEntryType;
  37
  38   static StringPoolEntryType &
  39   GetStringMapEntryFromKeyData(const char *keyData) {
  40     return StringPoolEntryType::GetStringMapEntryFromKeyData(keyData);
  41   }
  42
  43   static size_t GetConstCStringLength(const char *ccstr) {
  44     if (ccstr != nullptr) {
  45       // Since the entry is read only, and we derive the entry entirely from
  46       // the pointer, we don't need the lock.
  47       const StringPoolEntryType &entry = GetStringMapEntryFromKeyData(ccstr);
  48       return entry.getKey().size();
  49     }
  50     return 0;
  51   }
  52
  53   StringPoolValueType GetMangledCounterpart(const char *ccstr) const {
  54     if (ccstr != nullptr) {
  55       const uint8_t h = hash(llvm::StringRef(ccstr));
  56       llvm::sys::SmartScopedReader<false> rlock(m_string_pools[h].m_mutex);
  57       return GetStringMapEntryFromKeyData(ccstr).getValue();
  58     }
  59     return nullptr;
  60   }
  61
  62   bool SetMangledCounterparts(const char *key_ccstr, const char *value_ccstr) {
  63     if (key_ccstr != nullptr && value_ccstr != nullptr) {
  64       {
  65         const uint8_t h = hash(llvm::StringRef(key_ccstr));
  66         llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
  67         GetStringMapEntryFromKeyData(key_ccstr).setValue(value_ccstr);
  68       }
  69       {
  70         const uint8_t h = hash(llvm::StringRef(value_ccstr));
  71         llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
  72         GetStringMapEntryFromKeyData(value_ccstr).setValue(key_ccstr);
  73       }
  74       return true;
  75     }
  76     return false;
  77   }
  78
  79   const char *GetConstCString(const char *cstr) {
  80     if (cstr != nullptr)
  81       return GetConstCStringWithLength(cstr, strlen(cstr));
  82     return nullptr;
  83   }
  84
  85   const char *GetConstCStringWithLength(const char *cstr, size_t cstr_len) {
  86     if (cstr != nullptr)
  87       return GetConstCStringWithStringRef(llvm::StringRef(cstr, cstr_len));
  88     return nullptr;
  89   }
  90
  91   const char *GetConstCStringWithStringRef(const llvm::StringRef &string_ref) {
  92     if (string_ref.data()) {
  93       const uint8_t h = hash(string_ref);
  94
  95       {
  96         llvm::sys::SmartScopedReader<false> rlock(m_string_pools[h].m_mutex);
  97         auto it = m_string_pools[h].m_string_map.find(string_ref);
  98         if (it != m_string_pools[h].m_string_map.end())
  99           return it->getKeyData();
 100       }
 101
 102       llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
 103       StringPoolEntryType &entry =
 104           *m_string_pools[h]
 105                .m_string_map.insert(std::make_pair(string_ref, nullptr))
 106                .first;
 107       return entry.getKeyData();
 108     }
 109     return nullptr;
 110   }
 111
 112   const char *
 113   GetConstCStringAndSetMangledCounterPart(llvm::StringRef demangled,
 114                                           const char *mangled_ccstr) {
 115     const char *demangled_ccstr = nullptr;
 116
 117     {
 118       const uint8_t h = hash(demangled);
 119       llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
 120
 121       // Make or update string pool entry with the mangled counterpart
 122       StringPool &map = m_string_pools[h].m_string_map;
 123       StringPoolEntryType &entry = *map.try_emplace(demangled).first;
 124
 125       entry.second = mangled_ccstr;
 126
 127       // Extract the const version of the demangled_cstr
 128       demangled_ccstr = entry.getKeyData();
 129     }
 130
 131     {
 132       // Now assign the demangled const string as the counterpart of the
 133       // mangled const string...
 134       const uint8_t h = hash(llvm::StringRef(mangled_ccstr));
 135       llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
 136       GetStringMapEntryFromKeyData(mangled_ccstr).setValue(demangled_ccstr);
 137     }
 138
 139     // Return the constant demangled C string
 140     return demangled_ccstr;
 141   }
 142
 143   const char *GetConstTrimmedCStringWithLength(const char *cstr,
 144                                                size_t cstr_len) {
 145     if (cstr != nullptr) {
 146       const size_t trimmed_len = strnlen(cstr, cstr_len);
 147       return GetConstCStringWithLength(cstr, trimmed_len);
 148     }
 149     return nullptr;
 150   }
 151
 152   // Return the size in bytes that this object and any items in its collection
 153   // of uniqued strings + data count values takes in memory.
 154   size_t MemorySize() const {
 155     size_t mem_size = sizeof(Pool);
 156     for (const auto &pool : m_string_pools) {
 157       llvm::sys::SmartScopedReader<false> rlock(pool.m_mutex);
 158       for (const auto &entry : pool.m_string_map)
 159         mem_size += sizeof(StringPoolEntryType) + entry.getKey().size();
 160     }
 161     return mem_size;
 162   }
 163
 164 protected:
 165   uint8_t hash(const llvm::StringRef &s) const {
 166     uint32_t h = llvm::djbHash(s);
 167     return ((h >> 24) ^ (h >> 16) ^ (h >> 8) ^ h) & 0xff;
 168   }
 169
 170   struct PoolEntry {
 171     mutable llvm::sys::SmartRWMutex<false> m_mutex;
 172     StringPool m_string_map;
 173   };
 174
 175   std::array<PoolEntry, 256> m_string_pools;
 176 };
 177
 178 // Frameworks and dylibs aren't supposed to have global C++ initializers so we
 179 // hide the string pool in a static function so that it will get initialized on
 180 // the first call to this static function.
 181 //
 182 // Note, for now we make the string pool a pointer to the pool, because we
 183 // can't guarantee that some objects won't get destroyed after the global
 184 // destructor chain is run, and trying to make sure no destructors touch
 185 // ConstStrings is difficult.  So we leak the pool instead.
 186 static Pool &StringPool() {
 187   static llvm::once_flag g_pool_initialization_flag;
 188   static Pool *g_string_pool = nullptr;
 189
 190   llvm::call_once(g_pool_initialization_flag,
 191                  []() { g_string_pool = new Pool(); });
 192
 193   return *g_string_pool;
 194 }
 195
 196 ConstString::ConstString(const char *cstr)
 197     : m_string(StringPool().GetConstCString(cstr)) {}
 198
 199 ConstString::ConstString(const char *cstr, size_t cstr_len)
 200     : m_string(StringPool().GetConstCStringWithLength(cstr, cstr_len)) {}
 201
 202 ConstString::ConstString(const llvm::StringRef &s)
 203     : m_string(StringPool().GetConstCStringWithStringRef(s)) {}
 204
 205 bool ConstString::operator<(ConstString rhs) const {
 206   if (m_string == rhs.m_string)
 207     return false;
 208
 209   llvm::StringRef lhs_string_ref(GetStringRef());
 210   llvm::StringRef rhs_string_ref(rhs.GetStringRef());
 211
 212   // If both have valid C strings, then return the comparison
 213   if (lhs_string_ref.data() && rhs_string_ref.data())
 214     return lhs_string_ref < rhs_string_ref;
 215
 216   // Else one of them was nullptr, so if LHS is nullptr then it is less than
 217   return lhs_string_ref.data() == nullptr;
 218 }
 219
 220 Stream &lldb_private::operator<<(Stream &s, ConstString str) {
 221   const char *cstr = str.GetCString();
 222   if (cstr != nullptr)
 223     s << cstr;
 224
 225   return s;
 226 }
 227
 228 size_t ConstString::GetLength() const {
 229   return Pool::GetConstCStringLength(m_string);
 230 }
 231
 232 bool ConstString::Equals(ConstString lhs, ConstString rhs,
 233                          const bool case_sensitive) {
 234   if (lhs.m_string == rhs.m_string)
 235     return true;
 236
 237   // Since the pointers weren't equal, and identical ConstStrings always have
 238   // identical pointers, the result must be false for case sensitive equality
 239   // test.
 240   if (case_sensitive)
 241     return false;
 242
 243   // perform case insensitive equality test
 244   llvm::StringRef lhs_string_ref(lhs.GetStringRef());
 245   llvm::StringRef rhs_string_ref(rhs.GetStringRef());
 246   return lhs_string_ref.equals_lower(rhs_string_ref);
 247 }
 248
 249 int ConstString::Compare(ConstString lhs, ConstString rhs,
 250                          const bool case_sensitive) {
 251   // If the iterators are the same, this is the same string
 252   const char *lhs_cstr = lhs.m_string;
 253   const char *rhs_cstr = rhs.m_string;
 254   if (lhs_cstr == rhs_cstr)
 255     return 0;
 256   if (lhs_cstr && rhs_cstr) {
 257     llvm::StringRef lhs_string_ref(lhs.GetStringRef());
 258     llvm::StringRef rhs_string_ref(rhs.GetStringRef());
 259
 260     if (case_sensitive) {
 261       return lhs_string_ref.compare(rhs_string_ref);
 262     } else {
 263       return lhs_string_ref.compare_lower(rhs_string_ref);
 264     }
 265   }
 266
 267   if (lhs_cstr)
 268     return +1; // LHS isn't nullptr but RHS is
 269   else
 270     return -1; // LHS is nullptr but RHS isn't
 271 }
 272
 273 void ConstString::Dump(Stream *s, const char *fail_value) const {
 274   if (s != nullptr) {
 275     const char *cstr = AsCString(fail_value);
 276     if (cstr != nullptr)
 277       s->PutCString(cstr);
 278   }
 279 }
 280
 281 void ConstString::DumpDebug(Stream *s) const {
 282   const char *cstr = GetCString();
 283   size_t cstr_len = GetLength();
 284   // Only print the parens if we have a non-nullptr string
 285   const char *parens = cstr ? "\"" : "";
 286   s->Printf("%*p: ConstString, string = %s%s%s, length = %" PRIu64,
 287             static_cast<int>(sizeof(void *) * 2),
 288             static_cast<const void *>(this), parens, cstr, parens,
 289             static_cast<uint64_t>(cstr_len));
 290 }
 291
 292 void ConstString::SetCString(const char *cstr) {
 293   m_string = StringPool().GetConstCString(cstr);
 294 }
 295
 296 void ConstString::SetString(const llvm::StringRef &s) {
 297   m_string = StringPool().GetConstCStringWithLength(s.data(), s.size());
 298 }
 299
 300 void ConstString::SetStringWithMangledCounterpart(llvm::StringRef demangled,
 301                                                    ConstString mangled) {
 302   m_string = StringPool().GetConstCStringAndSetMangledCounterPart(
 303       demangled, mangled.m_string);
 304 }
 305
 306 bool ConstString::GetMangledCounterpart(ConstString &counterpart) const {
 307   counterpart.m_string = StringPool().GetMangledCounterpart(m_string);
 308   return (bool)counterpart;
 309 }
 310
 311 void ConstString::SetCStringWithLength(const char *cstr, size_t cstr_len) {
 312   m_string = StringPool().GetConstCStringWithLength(cstr, cstr_len);
 313 }
 314
 315 void ConstString::SetTrimmedCStringWithLength(const char *cstr,
 316                                               size_t cstr_len) {
 317   m_string = StringPool().GetConstTrimmedCStringWithLength(cstr, cstr_len);
 318 }
 319
 320 size_t ConstString::StaticMemorySize() {
 321   // Get the size of the static string pool
 322   return StringPool().MemorySize();
 323 }
 324
 325 void llvm::format_provider<ConstString>::format(const ConstString &CS,
 326                                                 llvm::raw_ostream &OS,
 327                                                 llvm::StringRef Options) {
 328   format_provider<StringRef>::format(CS.AsCString(), OS, Options);
 329 }