contrib/llvm/tools/lldb/source/Symbol/Symtab.cpp

   1 //===-- Symtab.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 <map>
  11 #include <set>
  12
  13 #include "Plugins/Language/CPlusPlus/CPlusPlusLanguage.h"
  14 #include "Plugins/Language/ObjC/ObjCLanguage.h"
  15 #include "lldb/Core/Module.h"
  16 #include "lldb/Core/RegularExpression.h"
  17 #include "lldb/Core/Section.h"
  18 #include "lldb/Core/Stream.h"
  19 #include "lldb/Core/Timer.h"
  20 #include "lldb/Symbol/ObjectFile.h"
  21 #include "lldb/Symbol/Symbol.h"
  22 #include "lldb/Symbol/SymbolContext.h"
  23 #include "lldb/Symbol/Symtab.h"
  24
  25 using namespace lldb;
  26 using namespace lldb_private;
  27
  28 Symtab::Symtab(ObjectFile *objfile)
  29     : m_objfile(objfile), m_symbols(), m_file_addr_to_index(),
  30       m_name_to_index(), m_mutex(), m_file_addr_to_index_computed(false),
  31       m_name_indexes_computed(false) {}
  32
  33 Symtab::~Symtab() {}
  34
  35 void Symtab::Reserve(size_t count) {
  36   // Clients should grab the mutex from this symbol table and lock it manually
  37   // when calling this function to avoid performance issues.
  38   m_symbols.reserve(count);
  39 }
  40
  41 Symbol *Symtab::Resize(size_t count) {
  42   // Clients should grab the mutex from this symbol table and lock it manually
  43   // when calling this function to avoid performance issues.
  44   m_symbols.resize(count);
  45   return m_symbols.empty() ? nullptr : &m_symbols[0];
  46 }
  47
  48 uint32_t Symtab::AddSymbol(const Symbol &symbol) {
  49   // Clients should grab the mutex from this symbol table and lock it manually
  50   // when calling this function to avoid performance issues.
  51   uint32_t symbol_idx = m_symbols.size();
  52   m_name_to_index.Clear();
  53   m_file_addr_to_index.Clear();
  54   m_symbols.push_back(symbol);
  55   m_file_addr_to_index_computed = false;
  56   m_name_indexes_computed = false;
  57   return symbol_idx;
  58 }
  59
  60 size_t Symtab::GetNumSymbols() const {
  61   std::lock_guard<std::recursive_mutex> guard(m_mutex);
  62   return m_symbols.size();
  63 }
  64
  65 void Symtab::SectionFileAddressesChanged() {
  66   m_name_to_index.Clear();
  67   m_file_addr_to_index_computed = false;
  68 }
  69
  70 void Symtab::Dump(Stream *s, Target *target, SortOrder sort_order) {
  71   std::lock_guard<std::recursive_mutex> guard(m_mutex);
  72
  73   //    s->Printf("%.*p: ", (int)sizeof(void*) * 2, this);
  74   s->Indent();
  75   const FileSpec &file_spec = m_objfile->GetFileSpec();
  76   const char *object_name = nullptr;
  77   if (m_objfile->GetModule())
  78     object_name = m_objfile->GetModule()->GetObjectName().GetCString();
  79
  80   if (file_spec)
  81     s->Printf("Symtab, file = %s%s%s%s, num_symbols = %" PRIu64,
  82               file_spec.GetPath().c_str(), object_name ? "(" : "",
  83               object_name ? object_name : "", object_name ? ")" : "",
  84               (uint64_t)m_symbols.size());
  85   else
  86     s->Printf("Symtab, num_symbols = %" PRIu64 "", (uint64_t)m_symbols.size());
  87
  88   if (!m_symbols.empty()) {
  89     switch (sort_order) {
  90     case eSortOrderNone: {
  91       s->PutCString(":\n");
  92       DumpSymbolHeader(s);
  93       const_iterator begin = m_symbols.begin();
  94       const_iterator end = m_symbols.end();
  95       for (const_iterator pos = m_symbols.begin(); pos != end; ++pos) {
  96         s->Indent();
  97         pos->Dump(s, target, std::distance(begin, pos));
  98       }
  99     } break;
 100
 101     case eSortOrderByName: {
 102       // Although we maintain a lookup by exact name map, the table
 103       // isn't sorted by name. So we must make the ordered symbol list
 104       // up ourselves.
 105       s->PutCString(" (sorted by name):\n");
 106       DumpSymbolHeader(s);
 107       typedef std::multimap<const char *, const Symbol *,
 108                             CStringCompareFunctionObject>
 109           CStringToSymbol;
 110       CStringToSymbol name_map;
 111       for (const_iterator pos = m_symbols.begin(), end = m_symbols.end();
 112            pos != end; ++pos) {
 113         const char *name = pos->GetName().AsCString();
 114         if (name && name[0])
 115           name_map.insert(std::make_pair(name, &(*pos)));
 116       }
 117
 118       for (CStringToSymbol::const_iterator pos = name_map.begin(),
 119                                            end = name_map.end();
 120            pos != end; ++pos) {
 121         s->Indent();
 122         pos->second->Dump(s, target, pos->second - &m_symbols[0]);
 123       }
 124     } break;
 125
 126     case eSortOrderByAddress:
 127       s->PutCString(" (sorted by address):\n");
 128       DumpSymbolHeader(s);
 129       if (!m_file_addr_to_index_computed)
 130         InitAddressIndexes();
 131       const size_t num_entries = m_file_addr_to_index.GetSize();
 132       for (size_t i = 0; i < num_entries; ++i) {
 133         s->Indent();
 134         const uint32_t symbol_idx = m_file_addr_to_index.GetEntryRef(i).data;
 135         m_symbols[symbol_idx].Dump(s, target, symbol_idx);
 136       }
 137       break;
 138     }
 139   }
 140 }
 141
 142 void Symtab::Dump(Stream *s, Target *target,
 143                   std::vector<uint32_t> &indexes) const {
 144   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 145
 146   const size_t num_symbols = GetNumSymbols();
 147   // s->Printf("%.*p: ", (int)sizeof(void*) * 2, this);
 148   s->Indent();
 149   s->Printf("Symtab %" PRIu64 " symbol indexes (%" PRIu64 " symbols total):\n",
 150             (uint64_t)indexes.size(), (uint64_t)m_symbols.size());
 151   s->IndentMore();
 152
 153   if (!indexes.empty()) {
 154     std::vector<uint32_t>::const_iterator pos;
 155     std::vector<uint32_t>::const_iterator end = indexes.end();
 156     DumpSymbolHeader(s);
 157     for (pos = indexes.begin(); pos != end; ++pos) {
 158       size_t idx = *pos;
 159       if (idx < num_symbols) {
 160         s->Indent();
 161         m_symbols[idx].Dump(s, target, idx);
 162       }
 163     }
 164   }
 165   s->IndentLess();
 166 }
 167
 168 void Symtab::DumpSymbolHeader(Stream *s) {
 169   s->Indent("               Debug symbol\n");
 170   s->Indent("               |Synthetic symbol\n");
 171   s->Indent("               ||Externally Visible\n");
 172   s->Indent("               |||\n");
 173   s->Indent("Index   UserID DSX Type            File Address/Value Load "
 174             "Address       Size               Flags      Name\n");
 175   s->Indent("------- ------ --- --------------- ------------------ "
 176             "------------------ ------------------ ---------- "
 177             "----------------------------------\n");
 178 }
 179
 180 static int CompareSymbolID(const void *key, const void *p) {
 181   const user_id_t match_uid = *(const user_id_t *)key;
 182   const user_id_t symbol_uid = ((const Symbol *)p)->GetID();
 183   if (match_uid < symbol_uid)
 184     return -1;
 185   if (match_uid > symbol_uid)
 186     return 1;
 187   return 0;
 188 }
 189
 190 Symbol *Symtab::FindSymbolByID(lldb::user_id_t symbol_uid) const {
 191   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 192
 193   Symbol *symbol =
 194       (Symbol *)::bsearch(&symbol_uid, &m_symbols[0], m_symbols.size(),
 195                           sizeof(m_symbols[0]), CompareSymbolID);
 196   return symbol;
 197 }
 198
 199 Symbol *Symtab::SymbolAtIndex(size_t idx) {
 200   // Clients should grab the mutex from this symbol table and lock it manually
 201   // when calling this function to avoid performance issues.
 202   if (idx < m_symbols.size())
 203     return &m_symbols[idx];
 204   return nullptr;
 205 }
 206
 207 const Symbol *Symtab::SymbolAtIndex(size_t idx) const {
 208   // Clients should grab the mutex from this symbol table and lock it manually
 209   // when calling this function to avoid performance issues.
 210   if (idx < m_symbols.size())
 211     return &m_symbols[idx];
 212   return nullptr;
 213 }
 214
 215 //----------------------------------------------------------------------
 216 // InitNameIndexes
 217 //----------------------------------------------------------------------
 218 void Symtab::InitNameIndexes() {
 219   // Protected function, no need to lock mutex...
 220   if (!m_name_indexes_computed) {
 221     m_name_indexes_computed = true;
 222     Timer scoped_timer(LLVM_PRETTY_FUNCTION, "%s", LLVM_PRETTY_FUNCTION);
 223     // Create the name index vector to be able to quickly search by name
 224     const size_t num_symbols = m_symbols.size();
 225 #if 1
 226     m_name_to_index.Reserve(num_symbols);
 227 #else
 228     // TODO: benchmark this to see if we save any memory. Otherwise we
 229     // will always keep the memory reserved in the vector unless we pull
 230     // some STL swap magic and then recopy...
 231     uint32_t actual_count = 0;
 232     for (const_iterator pos = m_symbols.begin(), end = m_symbols.end();
 233          pos != end; ++pos) {
 234       const Mangled &mangled = pos->GetMangled();
 235       if (mangled.GetMangledName())
 236         ++actual_count;
 237
 238       if (mangled.GetDemangledName())
 239         ++actual_count;
 240     }
 241
 242     m_name_to_index.Reserve(actual_count);
 243 #endif
 244
 245     NameToIndexMap::Entry entry;
 246
 247     // The "const char *" in "class_contexts" must come from a
 248     // ConstString::GetCString()
 249     std::set<const char *> class_contexts;
 250     UniqueCStringMap<uint32_t> mangled_name_to_index;
 251     std::vector<const char *> symbol_contexts(num_symbols, nullptr);
 252
 253     for (entry.value = 0; entry.value < num_symbols; ++entry.value) {
 254       const Symbol *symbol = &m_symbols[entry.value];
 255
 256       // Don't let trampolines get into the lookup by name map
 257       // If we ever need the trampoline symbols to be searchable by name
 258       // we can remove this and then possibly add a new bool to any of the
 259       // Symtab functions that lookup symbols by name to indicate if they
 260       // want trampolines.
 261       if (symbol->IsTrampoline())
 262         continue;
 263
 264       const Mangled &mangled = symbol->GetMangled();
 265       entry.cstring = mangled.GetMangledName().GetStringRef();
 266       if (!entry.cstring.empty()) {
 267         m_name_to_index.Append(entry);
 268
 269         if (symbol->ContainsLinkerAnnotations()) {
 270           // If the symbol has linker annotations, also add the version without
 271           // the annotations.
 272           entry.cstring = ConstString(m_objfile->StripLinkerSymbolAnnotations(
 273                                           entry.cstring))
 274                               .GetStringRef();
 275           m_name_to_index.Append(entry);
 276         }
 277
 278         const SymbolType symbol_type = symbol->GetType();
 279         if (symbol_type == eSymbolTypeCode ||
 280             symbol_type == eSymbolTypeResolver) {
 281           if (entry.cstring[0] == '_' && entry.cstring[1] == 'Z' &&
 282               (entry.cstring[2] != 'T' && // avoid virtual table, VTT structure,
 283                                           // typeinfo structure, and typeinfo
 284                                           // name
 285                entry.cstring[2] != 'G' && // avoid guard variables
 286                entry.cstring[2] != 'Z'))  // named local entities (if we
 287                                           // eventually handle eSymbolTypeData,
 288                                           // we will want this back)
 289           {
 290             CPlusPlusLanguage::MethodName cxx_method(
 291                 mangled.GetDemangledName(lldb::eLanguageTypeC_plus_plus));
 292             entry.cstring =
 293                 ConstString(cxx_method.GetBasename()).GetStringRef();
 294             if (!entry.cstring.empty()) {
 295               // ConstString objects permanently store the string in the pool so
 296               // calling
 297               // GetCString() on the value gets us a const char * that will
 298               // never go away
 299               const char *const_context =
 300                   ConstString(cxx_method.GetContext()).GetCString();
 301
 302               if (entry.cstring[0] == '~' ||
 303                   !cxx_method.GetQualifiers().empty()) {
 304                 // The first character of the demangled basename is '~' which
 305                 // means we have a class destructor. We can use this information
 306                 // to help us know what is a class and what isn't.
 307                 if (class_contexts.find(const_context) == class_contexts.end())
 308                   class_contexts.insert(const_context);
 309                 m_method_to_index.Append(entry);
 310               } else {
 311                 if (const_context && const_context[0]) {
 312                   if (class_contexts.find(const_context) !=
 313                       class_contexts.end()) {
 314                     // The current decl context is in our "class_contexts" which
 315                     // means
 316                     // this is a method on a class
 317                     m_method_to_index.Append(entry);
 318                   } else {
 319                     // We don't know if this is a function basename or a method,
 320                     // so put it into a temporary collection so once we are done
 321                     // we can look in class_contexts to see if each entry is a
 322                     // class
 323                     // or just a function and will put any remaining items into
 324                     // m_method_to_index or m_basename_to_index as needed
 325                     mangled_name_to_index.Append(entry);
 326                     symbol_contexts[entry.value] = const_context;
 327                   }
 328                 } else {
 329                   // No context for this function so this has to be a basename
 330                   m_basename_to_index.Append(entry);
 331                 }
 332               }
 333             }
 334           }
 335         }
 336       }
 337
 338       entry.cstring =
 339           mangled.GetDemangledName(symbol->GetLanguage()).GetStringRef();
 340       if (!entry.cstring.empty()) {
 341         m_name_to_index.Append(entry);
 342
 343         if (symbol->ContainsLinkerAnnotations()) {
 344           // If the symbol has linker annotations, also add the version without
 345           // the annotations.
 346           entry.cstring = ConstString(m_objfile->StripLinkerSymbolAnnotations(
 347                                           entry.cstring))
 348                               .GetStringRef();
 349           m_name_to_index.Append(entry);
 350         }
 351       }
 352
 353       // If the demangled name turns out to be an ObjC name, and
 354       // is a category name, add the version without categories to the index
 355       // too.
 356       ObjCLanguage::MethodName objc_method(entry.cstring, true);
 357       if (objc_method.IsValid(true)) {
 358         entry.cstring = objc_method.GetSelector().GetStringRef();
 359         m_selector_to_index.Append(entry);
 360
 361         ConstString objc_method_no_category(
 362             objc_method.GetFullNameWithoutCategory(true));
 363         if (objc_method_no_category) {
 364           entry.cstring = objc_method_no_category.GetStringRef();
 365           m_name_to_index.Append(entry);
 366         }
 367       }
 368     }
 369
 370     size_t count;
 371     if (!mangled_name_to_index.IsEmpty()) {
 372       count = mangled_name_to_index.GetSize();
 373       for (size_t i = 0; i < count; ++i) {
 374         if (mangled_name_to_index.GetValueAtIndex(i, entry.value)) {
 375           entry.cstring = mangled_name_to_index.GetCStringAtIndex(i);
 376           if (symbol_contexts[entry.value] &&
 377               class_contexts.find(symbol_contexts[entry.value]) !=
 378                   class_contexts.end()) {
 379             m_method_to_index.Append(entry);
 380           } else {
 381             // If we got here, we have something that had a context (was inside
 382             // a namespace or class)
 383             // yet we don't know if the entry
 384             m_method_to_index.Append(entry);
 385             m_basename_to_index.Append(entry);
 386           }
 387         }
 388       }
 389     }
 390     m_name_to_index.Sort();
 391     m_name_to_index.SizeToFit();
 392     m_selector_to_index.Sort();
 393     m_selector_to_index.SizeToFit();
 394     m_basename_to_index.Sort();
 395     m_basename_to_index.SizeToFit();
 396     m_method_to_index.Sort();
 397     m_method_to_index.SizeToFit();
 398
 399     //        static StreamFile a ("/tmp/a.txt");
 400     //
 401     //        count = m_basename_to_index.GetSize();
 402     //        if (count)
 403     //        {
 404     //            for (size_t i=0; i<count; ++i)
 405     //            {
 406     //                if (m_basename_to_index.GetValueAtIndex(i, entry.value))
 407     //                    a.Printf ("%s BASENAME\n",
 408     //                    m_symbols[entry.value].GetMangled().GetName().GetCString());
 409     //            }
 410     //        }
 411     //        count = m_method_to_index.GetSize();
 412     //        if (count)
 413     //        {
 414     //            for (size_t i=0; i<count; ++i)
 415     //            {
 416     //                if (m_method_to_index.GetValueAtIndex(i, entry.value))
 417     //                    a.Printf ("%s METHOD\n",
 418     //                    m_symbols[entry.value].GetMangled().GetName().GetCString());
 419     //            }
 420     //        }
 421   }
 422 }
 423
 424 void Symtab::AppendSymbolNamesToMap(const IndexCollection &indexes,
 425                                     bool add_demangled, bool add_mangled,
 426                                     NameToIndexMap &name_to_index_map) const {
 427   if (add_demangled || add_mangled) {
 428     Timer scoped_timer(LLVM_PRETTY_FUNCTION, "%s", LLVM_PRETTY_FUNCTION);
 429     std::lock_guard<std::recursive_mutex> guard(m_mutex);
 430
 431     // Create the name index vector to be able to quickly search by name
 432     NameToIndexMap::Entry entry;
 433     const size_t num_indexes = indexes.size();
 434     for (size_t i = 0; i < num_indexes; ++i) {
 435       entry.value = indexes[i];
 436       assert(i < m_symbols.size());
 437       const Symbol *symbol = &m_symbols[entry.value];
 438
 439       const Mangled &mangled = symbol->GetMangled();
 440       if (add_demangled) {
 441         entry.cstring =
 442             mangled.GetDemangledName(symbol->GetLanguage()).GetStringRef();
 443         if (!entry.cstring.empty())
 444           name_to_index_map.Append(entry);
 445       }
 446
 447       if (add_mangled) {
 448         entry.cstring = mangled.GetMangledName().GetStringRef();
 449         if (!entry.cstring.empty())
 450           name_to_index_map.Append(entry);
 451       }
 452     }
 453   }
 454 }
 455
 456 uint32_t Symtab::AppendSymbolIndexesWithType(SymbolType symbol_type,
 457                                              std::vector<uint32_t> &indexes,
 458                                              uint32_t start_idx,
 459                                              uint32_t end_index) const {
 460   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 461
 462   uint32_t prev_size = indexes.size();
 463
 464   const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index);
 465
 466   for (uint32_t i = start_idx; i < count; ++i) {
 467     if (symbol_type == eSymbolTypeAny || m_symbols[i].GetType() == symbol_type)
 468       indexes.push_back(i);
 469   }
 470
 471   return indexes.size() - prev_size;
 472 }
 473
 474 uint32_t Symtab::AppendSymbolIndexesWithTypeAndFlagsValue(
 475     SymbolType symbol_type, uint32_t flags_value,
 476     std::vector<uint32_t> &indexes, uint32_t start_idx,
 477     uint32_t end_index) const {
 478   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 479
 480   uint32_t prev_size = indexes.size();
 481
 482   const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index);
 483
 484   for (uint32_t i = start_idx; i < count; ++i) {
 485     if ((symbol_type == eSymbolTypeAny ||
 486          m_symbols[i].GetType() == symbol_type) &&
 487         m_symbols[i].GetFlags() == flags_value)
 488       indexes.push_back(i);
 489   }
 490
 491   return indexes.size() - prev_size;
 492 }
 493
 494 uint32_t Symtab::AppendSymbolIndexesWithType(SymbolType symbol_type,
 495                                              Debug symbol_debug_type,
 496                                              Visibility symbol_visibility,
 497                                              std::vector<uint32_t> &indexes,
 498                                              uint32_t start_idx,
 499                                              uint32_t end_index) const {
 500   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 501
 502   uint32_t prev_size = indexes.size();
 503
 504   const uint32_t count = std::min<uint32_t>(m_symbols.size(), end_index);
 505
 506   for (uint32_t i = start_idx; i < count; ++i) {
 507     if (symbol_type == eSymbolTypeAny ||
 508         m_symbols[i].GetType() == symbol_type) {
 509       if (CheckSymbolAtIndex(i, symbol_debug_type, symbol_visibility))
 510         indexes.push_back(i);
 511     }
 512   }
 513
 514   return indexes.size() - prev_size;
 515 }
 516
 517 uint32_t Symtab::GetIndexForSymbol(const Symbol *symbol) const {
 518   if (!m_symbols.empty()) {
 519     const Symbol *first_symbol = &m_symbols[0];
 520     if (symbol >= first_symbol && symbol < first_symbol + m_symbols.size())
 521       return symbol - first_symbol;
 522   }
 523   return UINT32_MAX;
 524 }
 525
 526 struct SymbolSortInfo {
 527   const bool sort_by_load_addr;
 528   const Symbol *symbols;
 529 };
 530
 531 namespace {
 532 struct SymbolIndexComparator {
 533   const std::vector<Symbol> &symbols;
 534   std::vector<lldb::addr_t> &addr_cache;
 535
 536   // Getting from the symbol to the Address to the File Address involves some
 537   // work.
 538   // Since there are potentially many symbols here, and we're using this for
 539   // sorting so
 540   // we're going to be computing the address many times, cache that in
 541   // addr_cache.
 542   // The array passed in has to be the same size as the symbols array passed
 543   // into the
 544   // member variable symbols, and should be initialized with
 545   // LLDB_INVALID_ADDRESS.
 546   // NOTE: You have to make addr_cache externally and pass it in because
 547   // std::stable_sort
 548   // makes copies of the comparator it is initially passed in, and you end up
 549   // spending
 550   // huge amounts of time copying this array...
 551
 552   SymbolIndexComparator(const std::vector<Symbol> &s,
 553                         std::vector<lldb::addr_t> &a)
 554       : symbols(s), addr_cache(a) {
 555     assert(symbols.size() == addr_cache.size());
 556   }
 557   bool operator()(uint32_t index_a, uint32_t index_b) {
 558     addr_t value_a = addr_cache[index_a];
 559     if (value_a == LLDB_INVALID_ADDRESS) {
 560       value_a = symbols[index_a].GetAddressRef().GetFileAddress();
 561       addr_cache[index_a] = value_a;
 562     }
 563
 564     addr_t value_b = addr_cache[index_b];
 565     if (value_b == LLDB_INVALID_ADDRESS) {
 566       value_b = symbols[index_b].GetAddressRef().GetFileAddress();
 567       addr_cache[index_b] = value_b;
 568     }
 569
 570     if (value_a == value_b) {
 571       // The if the values are equal, use the original symbol user ID
 572       lldb::user_id_t uid_a = symbols[index_a].GetID();
 573       lldb::user_id_t uid_b = symbols[index_b].GetID();
 574       if (uid_a < uid_b)
 575         return true;
 576       if (uid_a > uid_b)
 577         return false;
 578       return false;
 579     } else if (value_a < value_b)
 580       return true;
 581
 582     return false;
 583   }
 584 };
 585 }
 586
 587 void Symtab::SortSymbolIndexesByValue(std::vector<uint32_t> &indexes,
 588                                       bool remove_duplicates) const {
 589   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 590
 591   Timer scoped_timer(LLVM_PRETTY_FUNCTION, LLVM_PRETTY_FUNCTION);
 592   // No need to sort if we have zero or one items...
 593   if (indexes.size() <= 1)
 594     return;
 595
 596   // Sort the indexes in place using std::stable_sort.
 597   // NOTE: The use of std::stable_sort instead of std::sort here is strictly for
 598   // performance,
 599   // not correctness.  The indexes vector tends to be "close" to sorted, which
 600   // the
 601   // stable sort handles better.
 602
 603   std::vector<lldb::addr_t> addr_cache(m_symbols.size(), LLDB_INVALID_ADDRESS);
 604
 605   SymbolIndexComparator comparator(m_symbols, addr_cache);
 606   std::stable_sort(indexes.begin(), indexes.end(), comparator);
 607
 608   // Remove any duplicates if requested
 609   if (remove_duplicates)
 610     std::unique(indexes.begin(), indexes.end());
 611 }
 612
 613 uint32_t Symtab::AppendSymbolIndexesWithName(const ConstString &symbol_name,
 614                                              std::vector<uint32_t> &indexes) {
 615   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 616
 617   Timer scoped_timer(LLVM_PRETTY_FUNCTION, "%s", LLVM_PRETTY_FUNCTION);
 618   if (symbol_name) {
 619     if (!m_name_indexes_computed)
 620       InitNameIndexes();
 621
 622     return m_name_to_index.GetValues(symbol_name.GetStringRef(), indexes);
 623   }
 624   return 0;
 625 }
 626
 627 uint32_t Symtab::AppendSymbolIndexesWithName(const ConstString &symbol_name,
 628                                              Debug symbol_debug_type,
 629                                              Visibility symbol_visibility,
 630                                              std::vector<uint32_t> &indexes) {
 631   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 632
 633   Timer scoped_timer(LLVM_PRETTY_FUNCTION, "%s", LLVM_PRETTY_FUNCTION);
 634   if (symbol_name) {
 635     const size_t old_size = indexes.size();
 636     if (!m_name_indexes_computed)
 637       InitNameIndexes();
 638
 639     std::vector<uint32_t> all_name_indexes;
 640     const size_t name_match_count =
 641         m_name_to_index.GetValues(symbol_name.GetStringRef(), all_name_indexes);
 642     for (size_t i = 0; i < name_match_count; ++i) {
 643       if (CheckSymbolAtIndex(all_name_indexes[i], symbol_debug_type,
 644                              symbol_visibility))
 645         indexes.push_back(all_name_indexes[i]);
 646     }
 647     return indexes.size() - old_size;
 648   }
 649   return 0;
 650 }
 651
 652 uint32_t
 653 Symtab::AppendSymbolIndexesWithNameAndType(const ConstString &symbol_name,
 654                                            SymbolType symbol_type,
 655                                            std::vector<uint32_t> &indexes) {
 656   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 657
 658   if (AppendSymbolIndexesWithName(symbol_name, indexes) > 0) {
 659     std::vector<uint32_t>::iterator pos = indexes.begin();
 660     while (pos != indexes.end()) {
 661       if (symbol_type == eSymbolTypeAny ||
 662           m_symbols[*pos].GetType() == symbol_type)
 663         ++pos;
 664       else
 665         pos = indexes.erase(pos);
 666     }
 667   }
 668   return indexes.size();
 669 }
 670
 671 uint32_t Symtab::AppendSymbolIndexesWithNameAndType(
 672     const ConstString &symbol_name, SymbolType symbol_type,
 673     Debug symbol_debug_type, Visibility symbol_visibility,
 674     std::vector<uint32_t> &indexes) {
 675   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 676
 677   if (AppendSymbolIndexesWithName(symbol_name, symbol_debug_type,
 678                                   symbol_visibility, indexes) > 0) {
 679     std::vector<uint32_t>::iterator pos = indexes.begin();
 680     while (pos != indexes.end()) {
 681       if (symbol_type == eSymbolTypeAny ||
 682           m_symbols[*pos].GetType() == symbol_type)
 683         ++pos;
 684       else
 685         pos = indexes.erase(pos);
 686     }
 687   }
 688   return indexes.size();
 689 }
 690
 691 uint32_t Symtab::AppendSymbolIndexesMatchingRegExAndType(
 692     const RegularExpression &regexp, SymbolType symbol_type,
 693     std::vector<uint32_t> &indexes) {
 694   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 695
 696   uint32_t prev_size = indexes.size();
 697   uint32_t sym_end = m_symbols.size();
 698
 699   for (uint32_t i = 0; i < sym_end; i++) {
 700     if (symbol_type == eSymbolTypeAny ||
 701         m_symbols[i].GetType() == symbol_type) {
 702       const char *name = m_symbols[i].GetName().AsCString();
 703       if (name) {
 704         if (regexp.Execute(name))
 705           indexes.push_back(i);
 706       }
 707     }
 708   }
 709   return indexes.size() - prev_size;
 710 }
 711
 712 uint32_t Symtab::AppendSymbolIndexesMatchingRegExAndType(
 713     const RegularExpression &regexp, SymbolType symbol_type,
 714     Debug symbol_debug_type, Visibility symbol_visibility,
 715     std::vector<uint32_t> &indexes) {
 716   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 717
 718   uint32_t prev_size = indexes.size();
 719   uint32_t sym_end = m_symbols.size();
 720
 721   for (uint32_t i = 0; i < sym_end; i++) {
 722     if (symbol_type == eSymbolTypeAny ||
 723         m_symbols[i].GetType() == symbol_type) {
 724       if (CheckSymbolAtIndex(i, symbol_debug_type, symbol_visibility) == false)
 725         continue;
 726
 727       const char *name = m_symbols[i].GetName().AsCString();
 728       if (name) {
 729         if (regexp.Execute(name))
 730           indexes.push_back(i);
 731       }
 732     }
 733   }
 734   return indexes.size() - prev_size;
 735 }
 736
 737 Symbol *Symtab::FindSymbolWithType(SymbolType symbol_type,
 738                                    Debug symbol_debug_type,
 739                                    Visibility symbol_visibility,
 740                                    uint32_t &start_idx) {
 741   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 742
 743   const size_t count = m_symbols.size();
 744   for (size_t idx = start_idx; idx < count; ++idx) {
 745     if (symbol_type == eSymbolTypeAny ||
 746         m_symbols[idx].GetType() == symbol_type) {
 747       if (CheckSymbolAtIndex(idx, symbol_debug_type, symbol_visibility)) {
 748         start_idx = idx;
 749         return &m_symbols[idx];
 750       }
 751     }
 752   }
 753   return nullptr;
 754 }
 755
 756 size_t
 757 Symtab::FindAllSymbolsWithNameAndType(const ConstString &name,
 758                                       SymbolType symbol_type,
 759                                       std::vector<uint32_t> &symbol_indexes) {
 760   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 761
 762   Timer scoped_timer(LLVM_PRETTY_FUNCTION, "%s", LLVM_PRETTY_FUNCTION);
 763   // Initialize all of the lookup by name indexes before converting NAME
 764   // to a uniqued string NAME_STR below.
 765   if (!m_name_indexes_computed)
 766     InitNameIndexes();
 767
 768   if (name) {
 769     // The string table did have a string that matched, but we need
 770     // to check the symbols and match the symbol_type if any was given.
 771     AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_indexes);
 772   }
 773   return symbol_indexes.size();
 774 }
 775
 776 size_t Symtab::FindAllSymbolsWithNameAndType(
 777     const ConstString &name, SymbolType symbol_type, Debug symbol_debug_type,
 778     Visibility symbol_visibility, std::vector<uint32_t> &symbol_indexes) {
 779   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 780
 781   Timer scoped_timer(LLVM_PRETTY_FUNCTION, "%s", LLVM_PRETTY_FUNCTION);
 782   // Initialize all of the lookup by name indexes before converting NAME
 783   // to a uniqued string NAME_STR below.
 784   if (!m_name_indexes_computed)
 785     InitNameIndexes();
 786
 787   if (name) {
 788     // The string table did have a string that matched, but we need
 789     // to check the symbols and match the symbol_type if any was given.
 790     AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_debug_type,
 791                                        symbol_visibility, symbol_indexes);
 792   }
 793   return symbol_indexes.size();
 794 }
 795
 796 size_t Symtab::FindAllSymbolsMatchingRexExAndType(
 797     const RegularExpression &regex, SymbolType symbol_type,
 798     Debug symbol_debug_type, Visibility symbol_visibility,
 799     std::vector<uint32_t> &symbol_indexes) {
 800   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 801
 802   AppendSymbolIndexesMatchingRegExAndType(regex, symbol_type, symbol_debug_type,
 803                                           symbol_visibility, symbol_indexes);
 804   return symbol_indexes.size();
 805 }
 806
 807 Symbol *Symtab::FindFirstSymbolWithNameAndType(const ConstString &name,
 808                                                SymbolType symbol_type,
 809                                                Debug symbol_debug_type,
 810                                                Visibility symbol_visibility) {
 811   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 812
 813   Timer scoped_timer(LLVM_PRETTY_FUNCTION, "%s", LLVM_PRETTY_FUNCTION);
 814   if (!m_name_indexes_computed)
 815     InitNameIndexes();
 816
 817   if (name) {
 818     std::vector<uint32_t> matching_indexes;
 819     // The string table did have a string that matched, but we need
 820     // to check the symbols and match the symbol_type if any was given.
 821     if (AppendSymbolIndexesWithNameAndType(name, symbol_type, symbol_debug_type,
 822                                            symbol_visibility,
 823                                            matching_indexes)) {
 824       std::vector<uint32_t>::const_iterator pos, end = matching_indexes.end();
 825       for (pos = matching_indexes.begin(); pos != end; ++pos) {
 826         Symbol *symbol = SymbolAtIndex(*pos);
 827
 828         if (symbol->Compare(name, symbol_type))
 829           return symbol;
 830       }
 831     }
 832   }
 833   return nullptr;
 834 }
 835
 836 typedef struct {
 837   const Symtab *symtab;
 838   const addr_t file_addr;
 839   Symbol *match_symbol;
 840   const uint32_t *match_index_ptr;
 841   addr_t match_offset;
 842 } SymbolSearchInfo;
 843
 844 // Add all the section file start address & size to the RangeVector,
 845 // recusively adding any children sections.
 846 static void AddSectionsToRangeMap(SectionList *sectlist,
 847                                   RangeVector<addr_t, addr_t> &section_ranges) {
 848   const int num_sections = sectlist->GetNumSections(0);
 849   for (int i = 0; i < num_sections; i++) {
 850     SectionSP sect_sp = sectlist->GetSectionAtIndex(i);
 851     if (sect_sp) {
 852       SectionList &child_sectlist = sect_sp->GetChildren();
 853
 854       // If this section has children, add the children to the RangeVector.
 855       // Else add this section to the RangeVector.
 856       if (child_sectlist.GetNumSections(0) > 0) {
 857         AddSectionsToRangeMap(&child_sectlist, section_ranges);
 858       } else {
 859         size_t size = sect_sp->GetByteSize();
 860         if (size > 0) {
 861           addr_t base_addr = sect_sp->GetFileAddress();
 862           RangeVector<addr_t, addr_t>::Entry entry;
 863           entry.SetRangeBase(base_addr);
 864           entry.SetByteSize(size);
 865           section_ranges.Append(entry);
 866         }
 867       }
 868     }
 869   }
 870 }
 871
 872 void Symtab::InitAddressIndexes() {
 873   // Protected function, no need to lock mutex...
 874   if (!m_file_addr_to_index_computed && !m_symbols.empty()) {
 875     m_file_addr_to_index_computed = true;
 876
 877     FileRangeToIndexMap::Entry entry;
 878     const_iterator begin = m_symbols.begin();
 879     const_iterator end = m_symbols.end();
 880     for (const_iterator pos = m_symbols.begin(); pos != end; ++pos) {
 881       if (pos->ValueIsAddress()) {
 882         entry.SetRangeBase(pos->GetAddressRef().GetFileAddress());
 883         entry.SetByteSize(pos->GetByteSize());
 884         entry.data = std::distance(begin, pos);
 885         m_file_addr_to_index.Append(entry);
 886       }
 887     }
 888     const size_t num_entries = m_file_addr_to_index.GetSize();
 889     if (num_entries > 0) {
 890       m_file_addr_to_index.Sort();
 891
 892       // Create a RangeVector with the start & size of all the sections for
 893       // this objfile.  We'll need to check this for any FileRangeToIndexMap
 894       // entries with an uninitialized size, which could potentially be a
 895       // large number so reconstituting the weak pointer is busywork when it
 896       // is invariant information.
 897       SectionList *sectlist = m_objfile->GetSectionList();
 898       RangeVector<addr_t, addr_t> section_ranges;
 899       if (sectlist) {
 900         AddSectionsToRangeMap(sectlist, section_ranges);
 901         section_ranges.Sort();
 902       }
 903
 904       // Iterate through the FileRangeToIndexMap and fill in the size for any
 905       // entries that didn't already have a size from the Symbol (e.g. if we
 906       // have a plain linker symbol with an address only, instead of debug info
 907       // where we get an address and a size and a type, etc.)
 908       for (size_t i = 0; i < num_entries; i++) {
 909         FileRangeToIndexMap::Entry *entry =
 910             m_file_addr_to_index.GetMutableEntryAtIndex(i);
 911         if (entry->GetByteSize() == 0) {
 912           addr_t curr_base_addr = entry->GetRangeBase();
 913           const RangeVector<addr_t, addr_t>::Entry *containing_section =
 914               section_ranges.FindEntryThatContains(curr_base_addr);
 915
 916           // Use the end of the section as the default max size of the symbol
 917           addr_t sym_size = 0;
 918           if (containing_section) {
 919             sym_size =
 920                 containing_section->GetByteSize() -
 921                 (entry->GetRangeBase() - containing_section->GetRangeBase());
 922           }
 923
 924           for (size_t j = i; j < num_entries; j++) {
 925             FileRangeToIndexMap::Entry *next_entry =
 926                 m_file_addr_to_index.GetMutableEntryAtIndex(j);
 927             addr_t next_base_addr = next_entry->GetRangeBase();
 928             if (next_base_addr > curr_base_addr) {
 929               addr_t size_to_next_symbol = next_base_addr - curr_base_addr;
 930
 931               // Take the difference between this symbol and the next one as its
 932               // size,
 933               // if it is less than the size of the section.
 934               if (sym_size == 0 || size_to_next_symbol < sym_size) {
 935                 sym_size = size_to_next_symbol;
 936               }
 937               break;
 938             }
 939           }
 940
 941           if (sym_size > 0) {
 942             entry->SetByteSize(sym_size);
 943             Symbol &symbol = m_symbols[entry->data];
 944             symbol.SetByteSize(sym_size);
 945             symbol.SetSizeIsSynthesized(true);
 946           }
 947         }
 948       }
 949
 950       // Sort again in case the range size changes the ordering
 951       m_file_addr_to_index.Sort();
 952     }
 953   }
 954 }
 955
 956 void Symtab::CalculateSymbolSizes() {
 957   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 958
 959   if (!m_symbols.empty()) {
 960     if (!m_file_addr_to_index_computed)
 961       InitAddressIndexes();
 962
 963     const size_t num_entries = m_file_addr_to_index.GetSize();
 964
 965     for (size_t i = 0; i < num_entries; ++i) {
 966       // The entries in the m_file_addr_to_index have calculated the sizes
 967       // already
 968       // so we will use this size if we need to.
 969       const FileRangeToIndexMap::Entry &entry =
 970           m_file_addr_to_index.GetEntryRef(i);
 971
 972       Symbol &symbol = m_symbols[entry.data];
 973
 974       // If the symbol size is already valid, no need to do anything
 975       if (symbol.GetByteSizeIsValid())
 976         continue;
 977
 978       const addr_t range_size = entry.GetByteSize();
 979       if (range_size > 0) {
 980         symbol.SetByteSize(range_size);
 981         symbol.SetSizeIsSynthesized(true);
 982       }
 983     }
 984   }
 985 }
 986
 987 Symbol *Symtab::FindSymbolAtFileAddress(addr_t file_addr) {
 988   std::lock_guard<std::recursive_mutex> guard(m_mutex);
 989   if (!m_file_addr_to_index_computed)
 990     InitAddressIndexes();
 991
 992   const FileRangeToIndexMap::Entry *entry =
 993       m_file_addr_to_index.FindEntryStartsAt(file_addr);
 994   if (entry) {
 995     Symbol *symbol = SymbolAtIndex(entry->data);
 996     if (symbol->GetFileAddress() == file_addr)
 997       return symbol;
 998   }
 999   return nullptr;
1000 }
1001
1002 Symbol *Symtab::FindSymbolContainingFileAddress(addr_t file_addr) {
1003   std::lock_guard<std::recursive_mutex> guard(m_mutex);
1004
1005   if (!m_file_addr_to_index_computed)
1006     InitAddressIndexes();
1007
1008   const FileRangeToIndexMap::Entry *entry =
1009       m_file_addr_to_index.FindEntryThatContains(file_addr);
1010   if (entry) {
1011     Symbol *symbol = SymbolAtIndex(entry->data);
1012     if (symbol->ContainsFileAddress(file_addr))
1013       return symbol;
1014   }
1015   return nullptr;
1016 }
1017
1018 void Symtab::ForEachSymbolContainingFileAddress(
1019     addr_t file_addr, std::function<bool(Symbol *)> const &callback) {
1020   std::lock_guard<std::recursive_mutex> guard(m_mutex);
1021
1022   if (!m_file_addr_to_index_computed)
1023     InitAddressIndexes();
1024
1025   std::vector<uint32_t> all_addr_indexes;
1026
1027   // Get all symbols with file_addr
1028   const size_t addr_match_count =
1029       m_file_addr_to_index.FindEntryIndexesThatContain(file_addr,
1030                                                        all_addr_indexes);
1031
1032   for (size_t i = 0; i < addr_match_count; ++i) {
1033     Symbol *symbol = SymbolAtIndex(all_addr_indexes[i]);
1034     if (symbol->ContainsFileAddress(file_addr)) {
1035       if (!callback(symbol))
1036         break;
1037     }
1038   }
1039 }
1040
1041 void Symtab::SymbolIndicesToSymbolContextList(
1042     std::vector<uint32_t> &symbol_indexes, SymbolContextList &sc_list) {
1043   // No need to protect this call using m_mutex all other method calls are
1044   // already thread safe.
1045
1046   const bool merge_symbol_into_function = true;
1047   size_t num_indices = symbol_indexes.size();
1048   if (num_indices > 0) {
1049     SymbolContext sc;
1050     sc.module_sp = m_objfile->GetModule();
1051     for (size_t i = 0; i < num_indices; i++) {
1052       sc.symbol = SymbolAtIndex(symbol_indexes[i]);
1053       if (sc.symbol)
1054         sc_list.AppendIfUnique(sc, merge_symbol_into_function);
1055     }
1056   }
1057 }
1058
1059 size_t Symtab::FindFunctionSymbols(const ConstString &name,
1060                                    uint32_t name_type_mask,
1061                                    SymbolContextList &sc_list) {
1062   size_t count = 0;
1063   std::vector<uint32_t> symbol_indexes;
1064
1065   llvm::StringRef name_cstr = name.GetStringRef();
1066
1067   // eFunctionNameTypeAuto should be pre-resolved by a call to
1068   // Module::LookupInfo::LookupInfo()
1069   assert((name_type_mask & eFunctionNameTypeAuto) == 0);
1070
1071   if (name_type_mask & (eFunctionNameTypeBase | eFunctionNameTypeFull)) {
1072     std::vector<uint32_t> temp_symbol_indexes;
1073     FindAllSymbolsWithNameAndType(name, eSymbolTypeAny, temp_symbol_indexes);
1074
1075     unsigned temp_symbol_indexes_size = temp_symbol_indexes.size();
1076     if (temp_symbol_indexes_size > 0) {
1077       std::lock_guard<std::recursive_mutex> guard(m_mutex);
1078       for (unsigned i = 0; i < temp_symbol_indexes_size; i++) {
1079         SymbolContext sym_ctx;
1080         sym_ctx.symbol = SymbolAtIndex(temp_symbol_indexes[i]);
1081         if (sym_ctx.symbol) {
1082           switch (sym_ctx.symbol->GetType()) {
1083           case eSymbolTypeCode:
1084           case eSymbolTypeResolver:
1085           case eSymbolTypeReExported:
1086             symbol_indexes.push_back(temp_symbol_indexes[i]);
1087             break;
1088           default:
1089             break;
1090           }
1091         }
1092       }
1093     }
1094   }
1095
1096   if (name_type_mask & eFunctionNameTypeBase) {
1097     // From mangled names we can't tell what is a basename and what
1098     // is a method name, so we just treat them the same
1099     if (!m_name_indexes_computed)
1100       InitNameIndexes();
1101
1102     if (!m_basename_to_index.IsEmpty()) {
1103       const UniqueCStringMap<uint32_t>::Entry *match;
1104       for (match = m_basename_to_index.FindFirstValueForName(name_cstr);
1105            match != nullptr;
1106            match = m_basename_to_index.FindNextValueForName(match)) {
1107         symbol_indexes.push_back(match->value);
1108       }
1109     }
1110   }
1111
1112   if (name_type_mask & eFunctionNameTypeMethod) {
1113     if (!m_name_indexes_computed)
1114       InitNameIndexes();
1115
1116     if (!m_method_to_index.IsEmpty()) {
1117       const UniqueCStringMap<uint32_t>::Entry *match;
1118       for (match = m_method_to_index.FindFirstValueForName(name_cstr);
1119            match != nullptr;
1120            match = m_method_to_index.FindNextValueForName(match)) {
1121         symbol_indexes.push_back(match->value);
1122       }
1123     }
1124   }
1125
1126   if (name_type_mask & eFunctionNameTypeSelector) {
1127     if (!m_name_indexes_computed)
1128       InitNameIndexes();
1129
1130     if (!m_selector_to_index.IsEmpty()) {
1131       const UniqueCStringMap<uint32_t>::Entry *match;
1132       for (match = m_selector_to_index.FindFirstValueForName(name_cstr);
1133            match != nullptr;
1134            match = m_selector_to_index.FindNextValueForName(match)) {
1135         symbol_indexes.push_back(match->value);
1136       }
1137     }
1138   }
1139
1140   if (!symbol_indexes.empty()) {
1141     std::sort(symbol_indexes.begin(), symbol_indexes.end());
1142     symbol_indexes.erase(
1143         std::unique(symbol_indexes.begin(), symbol_indexes.end()),
1144         symbol_indexes.end());
1145     count = symbol_indexes.size();
1146     SymbolIndicesToSymbolContextList(symbol_indexes, sc_list);
1147   }
1148
1149   return count;
1150 }
1151
1152 const Symbol *Symtab::GetParent(Symbol *child_symbol) const {
1153   uint32_t child_idx = GetIndexForSymbol(child_symbol);
1154   if (child_idx != UINT32_MAX && child_idx > 0) {
1155     for (uint32_t idx = child_idx - 1; idx != UINT32_MAX; --idx) {
1156       const Symbol *symbol = SymbolAtIndex(idx);
1157       const uint32_t sibling_idx = symbol->GetSiblingIndex();
1158       if (sibling_idx != UINT32_MAX && sibling_idx > child_idx)
1159         return symbol;
1160     }
1161   }
1162   return NULL;
1163 }