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