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