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