contrib/llvm/tools/lldb/source/Utility/ConstString.cpp

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