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/StringExtras.h"
  15 #include "llvm/ADT/StringMap.h"
  16 #include "llvm/ADT/iterator.h"            // for iterator_facade_base
  17 #include "llvm/Support/Allocator.h"       // for BumpPtrAllocator
  18 #include "llvm/Support/FormatProviders.h" // for format_provider
  19 #include "llvm/Support/RWMutex.h"
  20 #include "llvm/Support/Threading.h"
  21
  22 #include <algorithm> // for min
  23 #include <array>
  24 #include <utility> // for make_pair, pair
  25
  26 #include <inttypes.h> // for PRIu64
  27 #include <stdint.h>   // for uint8_t, uint32_t, uint64_t
  28 #include <string.h>   // for size_t, strlen
  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 the
  47       // 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(const char *demangled_cstr,
 115                                           const char *mangled_ccstr) {
 116     if (demangled_cstr != nullptr) {
 117       const char *demangled_ccstr = nullptr;
 118
 119       {
 120         llvm::StringRef string_ref(demangled_cstr);
 121         const uint8_t h = hash(string_ref);
 122         llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
 123
 124         // Make string pool entry with the mangled counterpart already set
 125         StringPoolEntryType &entry =
 126             *m_string_pools[h]
 127                  .m_string_map.insert(std::make_pair(string_ref, mangled_ccstr))
 128                  .first;
 129
 130         // Extract the const version of the demangled_cstr
 131         demangled_ccstr = entry.getKeyData();
 132       }
 133
 134       {
 135         // Now assign the demangled const string as the counterpart of the
 136         // mangled const string...
 137         const uint8_t h = hash(llvm::StringRef(mangled_ccstr));
 138         llvm::sys::SmartScopedWriter<false> wlock(m_string_pools[h].m_mutex);
 139         GetStringMapEntryFromKeyData(mangled_ccstr).setValue(demangled_ccstr);
 140       }
 141
 142       // Return the constant demangled C string
 143       return demangled_ccstr;
 144     }
 145     return nullptr;
 146   }
 147
 148   const char *GetConstTrimmedCStringWithLength(const char *cstr,
 149                                                size_t cstr_len) {
 150     if (cstr != nullptr) {
 151       const size_t trimmed_len = std::min<size_t>(strlen(cstr), cstr_len);
 152       return GetConstCStringWithLength(cstr, trimmed_len);
 153     }
 154     return nullptr;
 155   }
 156
 157   //------------------------------------------------------------------
 158   // Return the size in bytes that this object and any items in its
 159   // collection of uniqued strings + data count values takes in
 160   // memory.
 161   //------------------------------------------------------------------
 162   size_t MemorySize() const {
 163     size_t mem_size = sizeof(Pool);
 164     for (const auto &pool : m_string_pools) {
 165       llvm::sys::SmartScopedReader<false> rlock(pool.m_mutex);
 166       for (const auto &entry : pool.m_string_map)
 167         mem_size += sizeof(StringPoolEntryType) + entry.getKey().size();
 168     }
 169     return mem_size;
 170   }
 171
 172 protected:
 173   uint8_t hash(const llvm::StringRef &s) const {
 174     uint32_t h = llvm::HashString(s);
 175     return ((h >> 24) ^ (h >> 16) ^ (h >> 8) ^ h) & 0xff;
 176   }
 177
 178   struct PoolEntry {
 179     mutable llvm::sys::SmartRWMutex<false> m_mutex;
 180     StringPool m_string_map;
 181   };
 182
 183   std::array<PoolEntry, 256> m_string_pools;
 184 };
 185
 186 //----------------------------------------------------------------------
 187 // Frameworks and dylibs aren't supposed to have global C++
 188 // initializers so we hide the string pool in a static function so
 189 // that it will get initialized on the first call to this static
 190 // function.
 191 //
 192 // Note, for now we make the string pool a pointer to the pool, because
 193 // we can't guarantee that some objects won't get destroyed after the
 194 // global destructor chain is run, and trying to make sure no destructors
 195 // touch ConstStrings is difficult.  So we leak the pool instead.
 196 //----------------------------------------------------------------------
 197 static Pool &StringPool() {
 198   static llvm::once_flag g_pool_initialization_flag;
 199   static Pool *g_string_pool = nullptr;
 200
 201   llvm::call_once(g_pool_initialization_flag,
 202                  []() { g_string_pool = new Pool(); });
 203
 204   return *g_string_pool;
 205 }
 206
 207 ConstString::ConstString(const char *cstr)
 208     : m_string(StringPool().GetConstCString(cstr)) {}
 209
 210 ConstString::ConstString(const char *cstr, size_t cstr_len)
 211     : m_string(StringPool().GetConstCStringWithLength(cstr, cstr_len)) {}
 212
 213 ConstString::ConstString(const llvm::StringRef &s)
 214     : m_string(StringPool().GetConstCStringWithLength(s.data(), s.size())) {}
 215
 216 bool ConstString::operator<(const ConstString &rhs) const {
 217   if (m_string == rhs.m_string)
 218     return false;
 219
 220   llvm::StringRef lhs_string_ref(GetStringRef());
 221   llvm::StringRef rhs_string_ref(rhs.GetStringRef());
 222
 223   // If both have valid C strings, then return the comparison
 224   if (lhs_string_ref.data() && rhs_string_ref.data())
 225     return lhs_string_ref < rhs_string_ref;
 226
 227   // Else one of them was nullptr, so if LHS is nullptr then it is less than
 228   return lhs_string_ref.data() == nullptr;
 229 }
 230
 231 Stream &lldb_private::operator<<(Stream &s, const ConstString &str) {
 232   const char *cstr = str.GetCString();
 233   if (cstr != nullptr)
 234     s << cstr;
 235
 236   return s;
 237 }
 238
 239 size_t ConstString::GetLength() const {
 240   return Pool::GetConstCStringLength(m_string);
 241 }
 242
 243 bool ConstString::Equals(const ConstString &lhs, const ConstString &rhs,
 244                          const bool case_sensitive) {
 245   if (lhs.m_string == rhs.m_string)
 246     return true;
 247
 248   // Since the pointers weren't equal, and identical ConstStrings always have
 249   // identical pointers,
 250   // the result must be false for case sensitive equality test.
 251   if (case_sensitive)
 252     return false;
 253
 254   // perform case insensitive equality test
 255   llvm::StringRef lhs_string_ref(lhs.GetStringRef());
 256   llvm::StringRef rhs_string_ref(rhs.GetStringRef());
 257   return lhs_string_ref.equals_lower(rhs_string_ref);
 258 }
 259
 260 int ConstString::Compare(const ConstString &lhs, const ConstString &rhs,
 261                          const bool case_sensitive) {
 262   // If the iterators are the same, this is the same string
 263   const char *lhs_cstr = lhs.m_string;
 264   const char *rhs_cstr = rhs.m_string;
 265   if (lhs_cstr == rhs_cstr)
 266     return 0;
 267   if (lhs_cstr && rhs_cstr) {
 268     llvm::StringRef lhs_string_ref(lhs.GetStringRef());
 269     llvm::StringRef rhs_string_ref(rhs.GetStringRef());
 270
 271     if (case_sensitive) {
 272       return lhs_string_ref.compare(rhs_string_ref);
 273     } else {
 274       return lhs_string_ref.compare_lower(rhs_string_ref);
 275     }
 276   }
 277
 278   if (lhs_cstr)
 279     return +1; // LHS isn't nullptr but RHS is
 280   else
 281     return -1; // LHS is nullptr but RHS isn't
 282 }
 283
 284 void ConstString::Dump(Stream *s, const char *fail_value) const {
 285   if (s != nullptr) {
 286     const char *cstr = AsCString(fail_value);
 287     if (cstr != nullptr)
 288       s->PutCString(cstr);
 289   }
 290 }
 291
 292 void ConstString::DumpDebug(Stream *s) const {
 293   const char *cstr = GetCString();
 294   size_t cstr_len = GetLength();
 295   // Only print the parens if we have a non-nullptr string
 296   const char *parens = cstr ? "\"" : "";
 297   s->Printf("%*p: ConstString, string = %s%s%s, length = %" PRIu64,
 298             static_cast<int>(sizeof(void *) * 2),
 299             static_cast<const void *>(this), parens, cstr, parens,
 300             static_cast<uint64_t>(cstr_len));
 301 }
 302
 303 void ConstString::SetCString(const char *cstr) {
 304   m_string = StringPool().GetConstCString(cstr);
 305 }
 306
 307 void ConstString::SetString(const llvm::StringRef &s) {
 308   m_string = StringPool().GetConstCStringWithLength(s.data(), s.size());
 309 }
 310
 311 void ConstString::SetCStringWithMangledCounterpart(const char *demangled,
 312                                                    const ConstString &mangled) {
 313   m_string = StringPool().GetConstCStringAndSetMangledCounterPart(
 314       demangled, mangled.m_string);
 315 }
 316
 317 bool ConstString::GetMangledCounterpart(ConstString &counterpart) const {
 318   counterpart.m_string = StringPool().GetMangledCounterpart(m_string);
 319   return (bool)counterpart;
 320 }
 321
 322 void ConstString::SetCStringWithLength(const char *cstr, size_t cstr_len) {
 323   m_string = StringPool().GetConstCStringWithLength(cstr, cstr_len);
 324 }
 325
 326 void ConstString::SetTrimmedCStringWithLength(const char *cstr,
 327                                               size_t cstr_len) {
 328   m_string = StringPool().GetConstTrimmedCStringWithLength(cstr, cstr_len);
 329 }
 330
 331 size_t ConstString::StaticMemorySize() {
 332   // Get the size of the static string pool
 333   return StringPool().MemorySize();
 334 }
 335
 336 void llvm::format_provider<ConstString>::format(const ConstString &CS,
 337                                                 llvm::raw_ostream &OS,
 338                                                 llvm::StringRef Options) {
 339   format_provider<StringRef>::format(CS.AsCString(), OS, Options);
 340 }