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
22using namespace lldb;
23using namespace lldb_private;
24
25
26
27Symtab::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
38Symtab::~Symtab()
39{
40}
41
42void
43Symtab::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
50Symbol *
51Symtab::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
59uint32_t
60Symtab::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
73size_t
74Symtab::GetNumSymbols() const
75{
76    Mutex::Locker locker (m_mutex);
77    return m_symbols.size();
78}
79
80void
81Symtab::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
161void
162Symtab::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
190void
191Symtab::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
202static int
203CompareSymbolID (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
214Symbol *
215Symtab::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
228Symbol *
229Symtab::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
239const Symbol *
240Symtab::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//----------------------------------------------------------------------
252void
253Symtab::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
443void
444Symtab::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
481uint32_t
482Symtab::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
499uint32_t
500Symtab::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
517uint32_t
518Symtab::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
539uint32_t
540Symtab::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
548struct SymbolSortInfo
549{
550    const bool sort_by_load_addr;
551    const Symbol *symbols;
552};
553
554namespace {
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
604void
605Symtab::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
629uint32_t
630Symtab::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
646uint32_t
647Symtab::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
672uint32_t
673Symtab::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
691uint32_t
692Symtab::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
711uint32_t
712Symtab::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
735uint32_t
736Symtab::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
762Symbol *
763Symtab::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
782size_t
783Symtab::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
802size_t
803Symtab::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
822size_t
823Symtab::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
831Symbol *
832Symtab::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
860typedef 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
869static int
870SymbolWithFileAddress (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
895static int
896SymbolWithClosestFileAddress (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
924static SymbolSearchInfo
925FindIndexPtrForSymbolContainingAddress(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
937void
938Symtab::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
997void
998Symtab::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
1031Symbol *
1032Symtab::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
1070Symbol *
1071Symtab::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
1084void
1085Symtab::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
1106size_t
1107Symtab::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
1212