contrib/llvm/tools/lldb/source/Plugins/SymbolFile/DWARF/HashedNameToDIE.h

   1 //===-- HashedNameToDIE.h ---------------------------------------*- 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 #ifndef SymbolFileDWARF_HashedNameToDIE_h_
  11 #define SymbolFileDWARF_HashedNameToDIE_h_
  12
  13 #include <vector>
  14
  15 #include "DWARFDefines.h"
  16 #include "DWARFFormValue.h"
  17
  18 #include "lldb/lldb-defines.h"
  19 #include "lldb/Core/dwarf.h"
  20 #include "lldb/Core/RegularExpression.h"
  21 #include "lldb/Core/MappedHash.h"
  22
  23
  24 class SymbolFileDWARF;
  25 class DWARFCompileUnit;
  26 class DWARFDebugInfoEntry;
  27
  28 struct DWARFMappedHash
  29 {
  30     struct DIEInfo
  31     {
  32         dw_offset_t offset;  // The DIE offset
  33         dw_tag_t tag;
  34         uint32_t type_flags; // Any flags for this DIEInfo
  35         uint32_t qualified_name_hash; // A 32 bit hash of the fully qualified name
  36
  37         DIEInfo () :
  38             offset (DW_INVALID_OFFSET),
  39             tag (0),
  40             type_flags (0),
  41             qualified_name_hash (0)
  42         {
  43         }
  44
  45         DIEInfo (dw_offset_t o, dw_tag_t t, uint32_t f, uint32_t h) :
  46             offset(o),
  47             tag (t),
  48             type_flags (f),
  49             qualified_name_hash (h)
  50         {
  51         }
  52
  53         void
  54         Clear()
  55         {
  56             offset = DW_INVALID_OFFSET;
  57             tag = 0;
  58             type_flags = 0;
  59             qualified_name_hash = 0;
  60         }
  61     };
  62
  63     typedef std::vector<DIEInfo> DIEInfoArray;
  64     typedef std::vector<uint32_t> DIEArray;
  65
  66     static void
  67     ExtractDIEArray (const DIEInfoArray &die_info_array,
  68                      DIEArray &die_offsets)
  69     {
  70         const size_t count = die_info_array.size();
  71         for (size_t i=0; i<count; ++i)
  72         {
  73             die_offsets.push_back (die_info_array[i].offset);
  74         }
  75     }
  76
  77     static void
  78     ExtractDIEArray (const DIEInfoArray &die_info_array,
  79                      const dw_tag_t tag,
  80                      DIEArray &die_offsets)
  81     {
  82         if (tag == 0)
  83         {
  84             ExtractDIEArray (die_info_array, die_offsets);
  85         }
  86         else
  87         {
  88             const size_t count = die_info_array.size();
  89             for (size_t i=0; i<count; ++i)
  90             {
  91                 const dw_tag_t die_tag = die_info_array[i].tag;
  92                 bool tag_matches = die_tag == 0 || tag == die_tag;
  93                 if (!tag_matches)
  94                 {
  95                     if (die_tag == DW_TAG_class_type || die_tag == DW_TAG_structure_type)
  96                         tag_matches = tag == DW_TAG_structure_type || tag == DW_TAG_class_type;
  97                 }
  98                 if (tag_matches)
  99                     die_offsets.push_back (die_info_array[i].offset);
 100             }
 101         }
 102     }
 103
 104     static void
 105     ExtractDIEArray (const DIEInfoArray &die_info_array,
 106                      const dw_tag_t tag,
 107                      const uint32_t qualified_name_hash,
 108                      DIEArray &die_offsets)
 109     {
 110         if (tag == 0)
 111         {
 112             ExtractDIEArray (die_info_array, die_offsets);
 113         }
 114         else
 115         {
 116             const size_t count = die_info_array.size();
 117             for (size_t i=0; i<count; ++i)
 118             {
 119                 if (qualified_name_hash != die_info_array[i].qualified_name_hash)
 120                     continue;
 121                 const dw_tag_t die_tag = die_info_array[i].tag;
 122                 bool tag_matches = die_tag == 0 || tag == die_tag;
 123                 if (!tag_matches)
 124                 {
 125                     if (die_tag == DW_TAG_class_type || die_tag == DW_TAG_structure_type)
 126                         tag_matches = tag == DW_TAG_structure_type || tag == DW_TAG_class_type;
 127                 }
 128                 if (tag_matches)
 129                     die_offsets.push_back (die_info_array[i].offset);
 130             }
 131         }
 132     }
 133
 134     enum AtomType
 135     {
 136         eAtomTypeNULL       = 0u,
 137         eAtomTypeDIEOffset  = 1u,   // DIE offset, check form for encoding
 138         eAtomTypeCUOffset   = 2u,   // DIE offset of the compiler unit header that contains the item in question
 139         eAtomTypeTag        = 3u,   // DW_TAG_xxx value, should be encoded as DW_FORM_data1 (if no tags exceed 255) or DW_FORM_data2
 140         eAtomTypeNameFlags  = 4u,   // Flags from enum NameFlags
 141         eAtomTypeTypeFlags  = 5u,   // Flags from enum TypeFlags,
 142         eAtomTypeQualNameHash = 6u  // A 32 bit hash of the full qualified name (since all hash entries are basename only)
 143                                     // For example a type like "std::vector<int>::iterator" would have a name of "iterator"
 144                                     // and a 32 bit hash for "std::vector<int>::iterator" to allow us to not have to pull
 145                                     // in debug info for a type when we know the fully qualified name.
 146     };
 147
 148     // Bit definitions for the eAtomTypeTypeFlags flags
 149     enum TypeFlags
 150     {
 151         // Always set for C++, only set for ObjC if this is the
 152         // @implementation for class
 153         eTypeFlagClassIsImplementation  = ( 1u << 1 )
 154     };
 155
 156
 157     static void
 158     ExtractClassOrStructDIEArray (const DIEInfoArray &die_info_array,
 159                                   bool return_implementation_only_if_available,
 160                                   DIEArray &die_offsets)
 161     {
 162         const size_t count = die_info_array.size();
 163         for (size_t i=0; i<count; ++i)
 164         {
 165             const dw_tag_t die_tag = die_info_array[i].tag;
 166             if (die_tag == 0 || die_tag == DW_TAG_class_type || die_tag == DW_TAG_structure_type)
 167             {
 168                 if (die_info_array[i].type_flags & eTypeFlagClassIsImplementation)
 169                 {
 170                     if (return_implementation_only_if_available)
 171                     {
 172                         // We found the one true definiton for this class, so
 173                         // only return that
 174                         die_offsets.clear();
 175                         die_offsets.push_back (die_info_array[i].offset);
 176                         return;
 177                     }
 178                     else
 179                     {
 180                         // Put the one true definition as the first entry so it
 181                         // matches first
 182                         die_offsets.insert (die_offsets.begin(), die_info_array[i].offset);
 183                     }
 184                 }
 185                 else
 186                 {
 187                     die_offsets.push_back (die_info_array[i].offset);
 188                 }
 189             }
 190         }
 191     }
 192
 193     static void
 194     ExtractTypesFromDIEArray (const DIEInfoArray &die_info_array,
 195                               uint32_t type_flag_mask,
 196                               uint32_t type_flag_value,
 197                               DIEArray &die_offsets)
 198     {
 199         const size_t count = die_info_array.size();
 200         for (size_t i=0; i<count; ++i)
 201         {
 202             if ((die_info_array[i].type_flags & type_flag_mask) == type_flag_value)
 203                 die_offsets.push_back (die_info_array[i].offset);
 204         }
 205     }
 206
 207     struct Atom
 208     {
 209         uint16_t type;
 210         dw_form_t form;
 211
 212         Atom (uint16_t t = eAtomTypeNULL, dw_form_t f = 0) :
 213             type (t),
 214             form (f)
 215         {
 216         }
 217     };
 218
 219     typedef std::vector<Atom> AtomArray;
 220
 221     static uint32_t
 222     GetTypeFlags (SymbolFileDWARF *dwarf2Data,
 223                   const DWARFCompileUnit* cu,
 224                   const DWARFDebugInfoEntry* die);
 225
 226
 227     static const char *
 228     GetAtomTypeName (uint16_t atom)
 229     {
 230         switch (atom)
 231         {
 232             case eAtomTypeNULL:         return "NULL";
 233             case eAtomTypeDIEOffset:    return "die-offset";
 234             case eAtomTypeCUOffset:     return "cu-offset";
 235             case eAtomTypeTag:          return "die-tag";
 236             case eAtomTypeNameFlags:    return "name-flags";
 237             case eAtomTypeTypeFlags:    return "type-flags";
 238             case eAtomTypeQualNameHash: return "qualified-name-hash";
 239         }
 240         return "<invalid>";
 241     }
 242     struct Prologue
 243     {
 244         // DIE offset base so die offsets in hash_data can be CU relative
 245         dw_offset_t die_base_offset;
 246         AtomArray atoms;
 247         uint32_t atom_mask;
 248         size_t min_hash_data_byte_size;
 249         bool hash_data_has_fixed_byte_size;
 250
 251         Prologue (dw_offset_t _die_base_offset = 0) :
 252             die_base_offset (_die_base_offset),
 253             atoms(),
 254             atom_mask (0),
 255             min_hash_data_byte_size(0),
 256             hash_data_has_fixed_byte_size(true)
 257         {
 258             // Define an array of DIE offsets by first defining an array,
 259             // and then define the atom type for the array, in this case
 260             // we have an array of DIE offsets
 261             AppendAtom (eAtomTypeDIEOffset, DW_FORM_data4);
 262         }
 263
 264         virtual ~Prologue()
 265         {
 266         }
 267
 268         void
 269         ClearAtoms ()
 270         {
 271             hash_data_has_fixed_byte_size = true;
 272             min_hash_data_byte_size = 0;
 273             atom_mask = 0;
 274             atoms.clear();
 275         }
 276
 277         bool
 278         ContainsAtom (AtomType atom_type) const
 279         {
 280             return (atom_mask & (1u << atom_type)) != 0;
 281         }
 282
 283         virtual void
 284         Clear ()
 285         {
 286             die_base_offset = 0;
 287             ClearAtoms ();
 288         }
 289
 290         void
 291         AppendAtom (AtomType type, dw_form_t form)
 292         {
 293             atoms.push_back (Atom(type, form));
 294             atom_mask |= 1u << type;
 295             switch (form)
 296             {
 297                 case DW_FORM_indirect:
 298                 case DW_FORM_exprloc:
 299                 case DW_FORM_flag_present:
 300                 case DW_FORM_ref_sig8:
 301                     assert (!"Unhandled atom form");
 302                     break;
 303
 304                 case DW_FORM_string:
 305                 case DW_FORM_block:
 306                 case DW_FORM_block1:
 307                 case DW_FORM_sdata:
 308                 case DW_FORM_udata:
 309                 case DW_FORM_ref_udata:
 310                     hash_data_has_fixed_byte_size = false;
 311                     // Fall through to the cases below...
 312                 case DW_FORM_flag:
 313                 case DW_FORM_data1:
 314                 case DW_FORM_ref1:
 315                 case DW_FORM_sec_offset:
 316                     min_hash_data_byte_size += 1;
 317                     break;
 318
 319                 case DW_FORM_block2:
 320                     hash_data_has_fixed_byte_size = false;
 321                     // Fall through to the cases below...
 322                 case DW_FORM_data2:
 323                 case DW_FORM_ref2:
 324                     min_hash_data_byte_size += 2;
 325                     break;
 326
 327                 case DW_FORM_block4:
 328                     hash_data_has_fixed_byte_size = false;
 329                     // Fall through to the cases below...
 330                 case DW_FORM_data4:
 331                 case DW_FORM_ref4:
 332                 case DW_FORM_addr:
 333                 case DW_FORM_ref_addr:
 334                 case DW_FORM_strp:
 335                     min_hash_data_byte_size += 4;
 336                     break;
 337
 338                 case DW_FORM_data8:
 339                 case DW_FORM_ref8:
 340                     min_hash_data_byte_size += 8;
 341                     break;
 342
 343             }
 344         }
 345
 346 //        void
 347 //        Dump (std::ostream* ostrm_ptr);
 348
 349         lldb::offset_t
 350         Read (const lldb_private::DataExtractor &data,
 351               lldb::offset_t offset)
 352         {
 353             ClearAtoms ();
 354
 355             die_base_offset = data.GetU32 (&offset);
 356
 357             const uint32_t atom_count = data.GetU32 (&offset);
 358             if (atom_count == 0x00060003u)
 359             {
 360                 // Old format, deal with contents of old pre-release format
 361                 while (data.GetU32(&offset))
 362                     /* do nothing */;
 363
 364                 // Hardcode to the only known value for now.
 365                 AppendAtom (eAtomTypeDIEOffset, DW_FORM_data4);
 366             }
 367             else
 368             {
 369                 for (uint32_t i=0; i<atom_count; ++i)
 370                 {
 371                     AtomType type = (AtomType)data.GetU16 (&offset);
 372                     dw_form_t form = (dw_form_t)data.GetU16 (&offset);
 373                     AppendAtom (type, form);
 374                 }
 375             }
 376             return offset;
 377         }
 378
 379 //        virtual void
 380 //        Write (BinaryStreamBuf &s);
 381
 382         size_t
 383         GetByteSize () const
 384         {
 385             // Add an extra count to the atoms size for the zero termination Atom that gets
 386             // written to disk
 387             return sizeof(die_base_offset) + sizeof(uint32_t) + atoms.size() * sizeof(Atom);
 388         }
 389
 390         size_t
 391         GetMinumumHashDataByteSize () const
 392         {
 393             return min_hash_data_byte_size;
 394         }
 395
 396         bool
 397         HashDataHasFixedByteSize() const
 398         {
 399             return hash_data_has_fixed_byte_size;
 400         }
 401     };
 402
 403     struct Header : public MappedHash::Header<Prologue>
 404     {
 405         Header (dw_offset_t _die_base_offset = 0)
 406         {
 407         }
 408
 409         virtual
 410         ~Header()
 411         {
 412         }
 413
 414         virtual size_t
 415         GetByteSize (const HeaderData &header_data)
 416         {
 417             return header_data.GetByteSize();
 418         }
 419
 420         //        virtual void
 421         //        Dump (std::ostream* ostrm_ptr);
 422         //
 423         virtual lldb::offset_t
 424         Read (lldb_private::DataExtractor &data, lldb::offset_t offset)
 425         {
 426             offset = MappedHash::Header<Prologue>::Read (data, offset);
 427             if (offset != UINT32_MAX)
 428             {
 429                 offset = header_data.Read (data, offset);
 430             }
 431             return offset;
 432         }
 433
 434         bool
 435         Read (const lldb_private::DataExtractor &data,
 436               lldb::offset_t *offset_ptr,
 437               DIEInfo &hash_data) const
 438         {
 439             const size_t num_atoms = header_data.atoms.size();
 440             if (num_atoms == 0)
 441                 return false;
 442
 443             for (size_t i=0; i<num_atoms; ++i)
 444             {
 445                 DWARFFormValue form_value (header_data.atoms[i].form);
 446
 447                 if (!form_value.ExtractValue(data, offset_ptr, NULL))
 448                     return false;
 449
 450                 switch (header_data.atoms[i].type)
 451                 {
 452                     case eAtomTypeDIEOffset:    // DIE offset, check form for encoding
 453                         hash_data.offset = (dw_offset_t)form_value.Reference (header_data.die_base_offset);
 454                         break;
 455
 456                     case eAtomTypeTag:          // DW_TAG value for the DIE
 457                         hash_data.tag = (dw_tag_t)form_value.Unsigned ();
 458
 459                     case eAtomTypeTypeFlags:    // Flags from enum TypeFlags
 460                         hash_data.type_flags = (uint32_t)form_value.Unsigned ();
 461                         break;
 462
 463                     case eAtomTypeQualNameHash:    // Flags from enum TypeFlags
 464                         hash_data.qualified_name_hash = form_value.Unsigned ();
 465                         break;
 466
 467                     default:
 468                         // We can always skip atomes we don't know about
 469                         break;
 470                 }
 471             }
 472             return true;
 473         }
 474
 475         void
 476         Dump (lldb_private::Stream& strm, const DIEInfo &hash_data) const
 477         {
 478             const size_t num_atoms = header_data.atoms.size();
 479             for (size_t i=0; i<num_atoms; ++i)
 480             {
 481                 if (i > 0)
 482                     strm.PutCString (", ");
 483
 484                 DWARFFormValue form_value (header_data.atoms[i].form);
 485                 switch (header_data.atoms[i].type)
 486                 {
 487                     case eAtomTypeDIEOffset:    // DIE offset, check form for encoding
 488                         strm.Printf ("{0x%8.8x}", hash_data.offset);
 489                         break;
 490
 491                     case eAtomTypeTag:          // DW_TAG value for the DIE
 492                         {
 493                             const char *tag_cstr = lldb_private::DW_TAG_value_to_name (hash_data.tag);
 494                             if (tag_cstr)
 495                                 strm.PutCString (tag_cstr);
 496                             else
 497                                 strm.Printf ("DW_TAG_(0x%4.4x)", hash_data.tag);
 498                         }
 499                         break;
 500
 501                     case eAtomTypeTypeFlags:    // Flags from enum TypeFlags
 502                         strm.Printf ("0x%2.2x", hash_data.type_flags);
 503                         if (hash_data.type_flags)
 504                         {
 505                             strm.PutCString (" (");
 506                             if (hash_data.type_flags & eTypeFlagClassIsImplementation)
 507                                 strm.PutCString (" implementation");
 508                             strm.PutCString (" )");
 509                         }
 510                         break;
 511
 512                     case eAtomTypeQualNameHash:    // Flags from enum TypeFlags
 513                         strm.Printf ("0x%8.8x", hash_data.qualified_name_hash);
 514                         break;
 515
 516                     default:
 517                         strm.Printf ("AtomType(0x%x)", header_data.atoms[i].type);
 518                         break;
 519                 }
 520             }
 521         }
 522     };
 523
 524 //    class ExportTable
 525 //    {
 526 //    public:
 527 //        ExportTable ();
 528 //
 529 //        void
 530 //        AppendNames (DWARFDebugPubnamesSet &pubnames_set,
 531 //                     StringTable &string_table);
 532 //
 533 //        void
 534 //        AppendNamesEntry (SymbolFileDWARF *dwarf2Data,
 535 //                          const DWARFCompileUnit* cu,
 536 //                          const DWARFDebugInfoEntry* die,
 537 //                          StringTable &string_table);
 538 //
 539 //        void
 540 //        AppendTypesEntry (DWARFData *dwarf2Data,
 541 //                          const DWARFCompileUnit* cu,
 542 //                          const DWARFDebugInfoEntry* die,
 543 //                          StringTable &string_table);
 544 //
 545 //        size_t
 546 //        Save (BinaryStreamBuf &names_data, const StringTable &string_table);
 547 //
 548 //        void
 549 //        AppendName (const char *name,
 550 //                    uint32_t die_offset,
 551 //                    StringTable &string_table,
 552 //                    dw_offset_t name_debug_str_offset = DW_INVALID_OFFSET); // If "name" has already been looked up, then it can be supplied
 553 //        void
 554 //        AppendType (const char *name,
 555 //                    uint32_t die_offset,
 556 //                    StringTable &string_table);
 557 //
 558 //
 559 //    protected:
 560 //        struct Entry
 561 //        {
 562 //            uint32_t hash;
 563 //            uint32_t str_offset;
 564 //            uint32_t die_offset;
 565 //        };
 566 //
 567 //        // Map uniqued .debug_str offset to the corresponding DIE offsets
 568 //        typedef std::map<uint32_t, DIEInfoArray> NameInfo;
 569 //        // Map a name hash to one or more name infos
 570 //        typedef std::map<uint32_t, NameInfo> BucketEntry;
 571 //
 572 //        static uint32_t
 573 //        GetByteSize (const NameInfo &name_info);
 574 //
 575 //        typedef std::vector<BucketEntry> BucketEntryColl;
 576 //        typedef std::vector<Entry> EntryColl;
 577 //        EntryColl m_entries;
 578 //
 579 //    };
 580
 581
 582     // A class for reading and using a saved hash table from a block of data
 583     // in memory
 584     class MemoryTable : public MappedHash::MemoryTable<uint32_t, DWARFMappedHash::Header, DIEInfoArray>
 585     {
 586     public:
 587
 588         MemoryTable (lldb_private::DataExtractor &table_data,
 589                      const lldb_private::DataExtractor &string_table,
 590                      const char *name) :
 591             MappedHash::MemoryTable<uint32_t, Header, DIEInfoArray> (table_data),
 592             m_data (table_data),
 593             m_string_table (string_table),
 594             m_name (name)
 595         {
 596         }
 597
 598         virtual
 599         ~MemoryTable ()
 600         {
 601         }
 602
 603         virtual const char *
 604         GetStringForKeyType (KeyType key) const
 605         {
 606             // The key in the DWARF table is the .debug_str offset for the string
 607             return m_string_table.PeekCStr (key);
 608         }
 609
 610         virtual bool
 611         ReadHashData (uint32_t hash_data_offset,
 612                       HashData &hash_data) const
 613         {
 614             lldb::offset_t offset = hash_data_offset;
 615             offset += 4; // Skip string table offset that contains offset of hash name in .debug_str
 616             const uint32_t count = m_data.GetU32 (&offset);
 617             if (count > 0)
 618             {
 619                 hash_data.resize(count);
 620                 for (uint32_t i=0; i<count; ++i)
 621                 {
 622                     if (!m_header.Read(m_data, &offset, hash_data[i]))
 623                         return false;
 624                 }
 625             }
 626             else
 627                 hash_data.clear();
 628             return true;
 629         }
 630
 631         virtual Result
 632         GetHashDataForName (const char *name,
 633                             lldb::offset_t* hash_data_offset_ptr,
 634                             Pair &pair) const
 635         {
 636             pair.key = m_data.GetU32 (hash_data_offset_ptr);
 637             pair.value.clear();
 638
 639             // If the key is zero, this terminates our chain of HashData objects
 640             // for this hash value.
 641             if (pair.key == 0)
 642                 return eResultEndOfHashData;
 643
 644             // There definitely should be a string for this string offset, if
 645             // there isn't, there is something wrong, return and error
 646             const char *strp_cstr = m_string_table.PeekCStr (pair.key);
 647             if (strp_cstr == NULL)
 648             {
 649                 *hash_data_offset_ptr = UINT32_MAX;
 650                 return eResultError;
 651             }
 652
 653             const uint32_t count = m_data.GetU32 (hash_data_offset_ptr);
 654             const size_t min_total_hash_data_size = count * m_header.header_data.GetMinumumHashDataByteSize();
 655             if (count > 0 && m_data.ValidOffsetForDataOfSize (*hash_data_offset_ptr, min_total_hash_data_size))
 656             {
 657                 // We have at least one HashData entry, and we have enough
 658                 // data to parse at leats "count" HashData enties.
 659
 660                 // First make sure the entire C string matches...
 661                 const bool match = strcmp (name, strp_cstr) == 0;
 662
 663                 if (!match && m_header.header_data.HashDataHasFixedByteSize())
 664                 {
 665                     // If the string doesn't match and we have fixed size data,
 666                     // we can just add the total byte size of all HashData objects
 667                     // to the hash data offset and be done...
 668                     *hash_data_offset_ptr += min_total_hash_data_size;
 669                 }
 670                 else
 671                 {
 672                     // If the string does match, or we don't have fixed size data
 673                     // then we need to read the hash data as a stream. If the
 674                     // string matches we also append all HashData objects to the
 675                     // value array.
 676                     for (uint32_t i=0; i<count; ++i)
 677                     {
 678                         DIEInfo die_info;
 679                         if (m_header.Read(m_data, hash_data_offset_ptr, die_info))
 680                         {
 681                             // Only happend the HashData if the string matched...
 682                             if (match)
 683                                 pair.value.push_back (die_info);
 684                         }
 685                         else
 686                         {
 687                             // Something went wrong while reading the data
 688                             *hash_data_offset_ptr = UINT32_MAX;
 689                             return eResultError;
 690                         }
 691                     }
 692                 }
 693                 // Return the correct response depending on if the string matched
 694                 // or not...
 695                 if (match)
 696                     return eResultKeyMatch;     // The key (cstring) matches and we have lookup results!
 697                 else
 698                     return eResultKeyMismatch;  // The key doesn't match, this function will get called
 699                                                 // again for the next key/value or the key terminator
 700                                                 // which in our case is a zero .debug_str offset.
 701             }
 702             else
 703             {
 704                 *hash_data_offset_ptr = UINT32_MAX;
 705                 return eResultError;
 706             }
 707         }
 708
 709         virtual Result
 710         AppendHashDataForRegularExpression (const lldb_private::RegularExpression& regex,
 711                                             lldb::offset_t* hash_data_offset_ptr,
 712                                             Pair &pair) const
 713         {
 714             pair.key = m_data.GetU32 (hash_data_offset_ptr);
 715             // If the key is zero, this terminates our chain of HashData objects
 716             // for this hash value.
 717             if (pair.key == 0)
 718                 return eResultEndOfHashData;
 719
 720             // There definitely should be a string for this string offset, if
 721             // there isn't, there is something wrong, return and error
 722             const char *strp_cstr = m_string_table.PeekCStr (pair.key);
 723             if (strp_cstr == NULL)
 724                 return eResultError;
 725
 726             const uint32_t count = m_data.GetU32 (hash_data_offset_ptr);
 727             const size_t min_total_hash_data_size = count * m_header.header_data.GetMinumumHashDataByteSize();
 728             if (count > 0 && m_data.ValidOffsetForDataOfSize (*hash_data_offset_ptr, min_total_hash_data_size))
 729             {
 730                 const bool match = regex.Execute(strp_cstr);
 731
 732                 if (!match && m_header.header_data.HashDataHasFixedByteSize())
 733                 {
 734                     // If the regex doesn't match and we have fixed size data,
 735                     // we can just add the total byte size of all HashData objects
 736                     // to the hash data offset and be done...
 737                     *hash_data_offset_ptr += min_total_hash_data_size;
 738                 }
 739                 else
 740                 {
 741                     // If the string does match, or we don't have fixed size data
 742                     // then we need to read the hash data as a stream. If the
 743                     // string matches we also append all HashData objects to the
 744                     // value array.
 745                     for (uint32_t i=0; i<count; ++i)
 746                     {
 747                         DIEInfo die_info;
 748                         if (m_header.Read(m_data, hash_data_offset_ptr, die_info))
 749                         {
 750                             // Only happend the HashData if the string matched...
 751                             if (match)
 752                                 pair.value.push_back (die_info);
 753                         }
 754                         else
 755                         {
 756                             // Something went wrong while reading the data
 757                             *hash_data_offset_ptr = UINT32_MAX;
 758                             return eResultError;
 759                         }
 760                     }
 761                 }
 762                 // Return the correct response depending on if the string matched
 763                 // or not...
 764                 if (match)
 765                     return eResultKeyMatch;     // The key (cstring) matches and we have lookup results!
 766                 else
 767                     return eResultKeyMismatch;  // The key doesn't match, this function will get called
 768                                                 // again for the next key/value or the key terminator
 769                                                 // which in our case is a zero .debug_str offset.
 770             }
 771             else
 772             {
 773                 *hash_data_offset_ptr = UINT32_MAX;
 774                 return eResultError;
 775             }
 776         }
 777
 778         size_t
 779         AppendAllDIEsThatMatchingRegex (const lldb_private::RegularExpression& regex,
 780                                         DIEInfoArray &die_info_array) const
 781         {
 782             const uint32_t hash_count = m_header.hashes_count;
 783             Pair pair;
 784             for (uint32_t offset_idx=0; offset_idx<hash_count; ++offset_idx)
 785             {
 786                 lldb::offset_t hash_data_offset = GetHashDataOffset (offset_idx);
 787                 while (hash_data_offset != UINT32_MAX)
 788                 {
 789                     const lldb::offset_t prev_hash_data_offset = hash_data_offset;
 790                     Result hash_result = AppendHashDataForRegularExpression (regex, &hash_data_offset, pair);
 791                     if (prev_hash_data_offset == hash_data_offset)
 792                         break;
 793
 794                     // Check the result of getting our hash data
 795                     switch (hash_result)
 796                     {
 797                         case eResultKeyMatch:
 798                         case eResultKeyMismatch:
 799                             // Whether we matches or not, it doesn't matter, we
 800                             // keep looking.
 801                             break;
 802
 803                         case eResultEndOfHashData:
 804                         case eResultError:
 805                             hash_data_offset = UINT32_MAX;
 806                             break;
 807                     }
 808                 }
 809             }
 810             die_info_array.swap (pair.value);
 811             return die_info_array.size();
 812         }
 813
 814         size_t
 815         AppendAllDIEsInRange (const uint32_t die_offset_start,
 816                               const uint32_t die_offset_end,
 817                               DIEInfoArray &die_info_array) const
 818         {
 819             const uint32_t hash_count = m_header.hashes_count;
 820             for (uint32_t offset_idx=0; offset_idx<hash_count; ++offset_idx)
 821             {
 822                 bool done = false;
 823                 lldb::offset_t hash_data_offset = GetHashDataOffset (offset_idx);
 824                 while (!done && hash_data_offset != UINT32_MAX)
 825                 {
 826                     KeyType key = m_data.GetU32 (&hash_data_offset);
 827                     // If the key is zero, this terminates our chain of HashData objects
 828                     // for this hash value.
 829                     if (key == 0)
 830                         break;
 831
 832                     const uint32_t count = m_data.GetU32 (&hash_data_offset);
 833                     for (uint32_t i=0; i<count; ++i)
 834                     {
 835                         DIEInfo die_info;
 836                         if (m_header.Read(m_data, &hash_data_offset, die_info))
 837                         {
 838                             if (die_info.offset == 0)
 839                                 done = true;
 840                             if (die_offset_start <= die_info.offset && die_info.offset < die_offset_end)
 841                                 die_info_array.push_back(die_info);
 842                         }
 843                     }
 844                 }
 845             }
 846             return die_info_array.size();
 847         }
 848
 849         size_t
 850         FindByName (const char *name, DIEArray &die_offsets)
 851         {
 852             DIEInfoArray die_info_array;
 853             if (FindByName(name, die_info_array))
 854                 DWARFMappedHash::ExtractDIEArray (die_info_array, die_offsets);
 855             return die_info_array.size();
 856         }
 857
 858         size_t
 859         FindByNameAndTag (const char *name,
 860                           const dw_tag_t tag,
 861                           DIEArray &die_offsets)
 862         {
 863             DIEInfoArray die_info_array;
 864             if (FindByName(name, die_info_array))
 865                 DWARFMappedHash::ExtractDIEArray (die_info_array, tag, die_offsets);
 866             return die_info_array.size();
 867         }
 868
 869         size_t
 870         FindByNameAndTagAndQualifiedNameHash (const char *name,
 871                                               const dw_tag_t tag,
 872                                               const uint32_t qualified_name_hash,
 873                                               DIEArray &die_offsets)
 874         {
 875             DIEInfoArray die_info_array;
 876             if (FindByName(name, die_info_array))
 877                 DWARFMappedHash::ExtractDIEArray (die_info_array, tag, qualified_name_hash, die_offsets);
 878             return die_info_array.size();
 879         }
 880
 881         size_t
 882         FindCompleteObjCClassByName (const char *name, DIEArray &die_offsets, bool must_be_implementation)
 883         {
 884             DIEInfoArray die_info_array;
 885             if (FindByName(name, die_info_array))
 886             {
 887                 if (must_be_implementation && GetHeader().header_data.ContainsAtom (eAtomTypeTypeFlags))
 888                 {
 889                     // If we have two atoms, then we have the DIE offset and
 890                     // the type flags so we can find the objective C class
 891                     // efficiently.
 892                     DWARFMappedHash::ExtractTypesFromDIEArray (die_info_array,
 893                                                                UINT32_MAX,
 894                                                                eTypeFlagClassIsImplementation,
 895                                                                die_offsets);
 896                 }
 897                 else
 898                 {
 899                     // We don't only want the one true definition, so try and see
 900                     // what we can find, and only return class or struct DIEs.
 901                     // If we do have the full implementation, then return it alone,
 902                     // else return all possible matches.
 903                     const bool return_implementation_only_if_available = true;
 904                     DWARFMappedHash::ExtractClassOrStructDIEArray (die_info_array,
 905                                                                    return_implementation_only_if_available,
 906                                                                    die_offsets);
 907                 }
 908             }
 909             return die_offsets.size();
 910         }
 911
 912         size_t
 913         FindByName (const char *name, DIEInfoArray &die_info_array)
 914         {
 915             Pair kv_pair;
 916             size_t old_size = die_info_array.size();
 917             if (Find (name, kv_pair))
 918             {
 919                 die_info_array.swap(kv_pair.value);
 920                 return die_info_array.size() - old_size;
 921             }
 922             return 0;
 923         }
 924
 925     protected:
 926         const lldb_private::DataExtractor &m_data;
 927         const lldb_private::DataExtractor &m_string_table;
 928         std::string m_name;
 929     };
 930 };
 931
 932
 933 #endif  // SymbolFileDWARF_HashedNameToDIE_h_