source/Plugins/SymbolFile/DWARF/HashedNameToDIE.cpp - lldb - Git at Google

 //===-- HashedNameToDIE.cpp -------------------------------------*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//

 #include "HashedNameToDIE.h"

 void
 DWARFMappedHash::ExtractDIEArray (const DIEInfoArray &die_info_array, DIEArray &die_offsets)
 {
     const size_t count = die_info_array.size();
     for (size_t i=0; i<count; ++i)
         die_offsets.emplace_back(die_info_array[i].cu_offset, die_info_array[i].offset);
 }

 void
 DWARFMappedHash::ExtractDIEArray (const DIEInfoArray &die_info_array,
                                   const dw_tag_t tag,
                                   DIEArray &die_offsets)
 {
     if (tag == 0)
     {
         ExtractDIEArray (die_info_array, die_offsets);
     }
     else
     {
         const size_t count = die_info_array.size();
         for (size_t i=0; i<count; ++i)
         {
             const dw_tag_t die_tag = die_info_array[i].tag;
             bool tag_matches = die_tag == 0 || tag == die_tag;
             if (!tag_matches)
             {
                 if (die_tag == DW_TAG_class_type || die_tag == DW_TAG_structure_type)
                     tag_matches = tag == DW_TAG_structure_type || tag == DW_TAG_class_type;
             }
             if (tag_matches)
                 die_offsets.emplace_back(die_info_array[i].cu_offset, die_info_array[i].offset);
         }
     }
 }

 void
 DWARFMappedHash::ExtractDIEArray (const DIEInfoArray &die_info_array,
                                   const dw_tag_t tag,
                                   const uint32_t qualified_name_hash,
                                   DIEArray &die_offsets)
 {
     if (tag == 0)
     {
         ExtractDIEArray (die_info_array, die_offsets);
     }
     else
     {
         const size_t count = die_info_array.size();
         for (size_t i=0; i<count; ++i)
         {
             if (qualified_name_hash != die_info_array[i].qualified_name_hash)
                 continue;
             const dw_tag_t die_tag = die_info_array[i].tag;
             bool tag_matches = die_tag == 0 || tag == die_tag;
             if (!tag_matches)
             {
                 if (die_tag == DW_TAG_class_type || die_tag == DW_TAG_structure_type)
                     tag_matches = tag == DW_TAG_structure_type || tag == DW_TAG_class_type;
             }
             if (tag_matches)
                 die_offsets.emplace_back(die_info_array[i].cu_offset, die_info_array[i].offset);
         }
     }
 }

 void
 DWARFMappedHash::ExtractClassOrStructDIEArray (const DIEInfoArray &die_info_array,
                                                bool return_implementation_only_if_available,
                                                DIEArray &die_offsets)
 {
     const size_t count = die_info_array.size();
     for (size_t i=0; i<count; ++i)
     {
         const dw_tag_t die_tag = die_info_array[i].tag;
         if (die_tag == 0 || die_tag == DW_TAG_class_type || die_tag == DW_TAG_structure_type)
         {
             if (die_info_array[i].type_flags & eTypeFlagClassIsImplementation)
             {
                 if (return_implementation_only_if_available)
                 {
                     // We found the one true definition for this class, so
                     // only return that
                     die_offsets.clear();
                     die_offsets.emplace_back(die_info_array[i].cu_offset, die_info_array[i].offset);
                     return;
                 }
                 else
                 {
                     // Put the one true definition as the first entry so it
                     // matches first
                     die_offsets.emplace(die_offsets.begin(), die_info_array[i].cu_offset, die_info_array[i].offset);
                 }
             }
             else
             {
                 die_offsets.emplace_back(die_info_array[i].cu_offset, die_info_array[i].offset);
             }
         }
     }
 }

 void
 DWARFMappedHash::ExtractTypesFromDIEArray (const DIEInfoArray &die_info_array,
                                            uint32_t type_flag_mask,
                                            uint32_t type_flag_value,
                                            DIEArray &die_offsets)
 {
     const size_t count = die_info_array.size();
     for (size_t i=0; i<count; ++i)
     {
         if ((die_info_array[i].type_flags & type_flag_mask) == type_flag_value)
             die_offsets.emplace_back(die_info_array[i].cu_offset, die_info_array[i].offset);
     }
 }

 const char *
 DWARFMappedHash::GetAtomTypeName (uint16_t atom)
 {
     switch (atom)
     {
         case eAtomTypeNULL:         return "NULL";
         case eAtomTypeDIEOffset:    return "die-offset";
         case eAtomTypeCUOffset:     return "cu-offset";
         case eAtomTypeTag:          return "die-tag";
         case eAtomTypeNameFlags:    return "name-flags";
         case eAtomTypeTypeFlags:    return "type-flags";
         case eAtomTypeQualNameHash: return "qualified-name-hash";
     }
     return "<invalid>";
 }

 DWARFMappedHash::DIEInfo::DIEInfo () :
     cu_offset (DW_INVALID_OFFSET),
     offset (DW_INVALID_OFFSET),
     tag (0),
     type_flags (0),
     qualified_name_hash (0)
 {
 }

 DWARFMappedHash::DIEInfo::DIEInfo (dw_offset_t c,
                                    dw_offset_t o,
                                    dw_tag_t t,
                                    uint32_t f,
                                    uint32_t h) :
     cu_offset (c),
     offset (o),
     tag (t),
     type_flags (f),
     qualified_name_hash (h)
 {
 }

 DWARFMappedHash::Prologue::Prologue (dw_offset_t _die_base_offset) :
     die_base_offset (_die_base_offset),
     atoms(),
     atom_mask (0),
     min_hash_data_byte_size(0),
     hash_data_has_fixed_byte_size(true)
 {
     // Define an array of DIE offsets by first defining an array,
     // and then define the atom type for the array, in this case
     // we have an array of DIE offsets
     AppendAtom (eAtomTypeDIEOffset, DW_FORM_data4);
 }

 void
 DWARFMappedHash::Prologue::ClearAtoms ()
 {
     hash_data_has_fixed_byte_size = true;
     min_hash_data_byte_size = 0;
     atom_mask = 0;
     atoms.clear();
 }

 bool
 DWARFMappedHash::Prologue::ContainsAtom (AtomType atom_type) const
 {
     return (atom_mask & (1u << atom_type)) != 0;
 }

 void
 DWARFMappedHash::Prologue::Clear ()
 {
     die_base_offset = 0;
     ClearAtoms ();
 }

 void
 DWARFMappedHash::Prologue::AppendAtom (AtomType type, dw_form_t form)
 {
     atoms.push_back ({type, form});
     atom_mask |= 1u << type;
     switch (form)
     {
         case DW_FORM_indirect:
         case DW_FORM_exprloc:
         case DW_FORM_flag_present:
         case DW_FORM_ref_sig8:
             assert (!"Unhandled atom form");
             break;

         case DW_FORM_string:
         case DW_FORM_block:
         case DW_FORM_block1:
         case DW_FORM_sdata:
         case DW_FORM_udata:
         case DW_FORM_ref_udata:
         case DW_FORM_GNU_addr_index:
         case DW_FORM_GNU_str_index:
             hash_data_has_fixed_byte_size = false;
             // Fall through to the cases below...
         case DW_FORM_flag:
         case DW_FORM_data1:
         case DW_FORM_ref1:
         case DW_FORM_sec_offset:
             min_hash_data_byte_size += 1;
             break;

         case DW_FORM_block2:
             hash_data_has_fixed_byte_size = false;
             // Fall through to the cases below...
         case DW_FORM_data2:
         case DW_FORM_ref2:
             min_hash_data_byte_size += 2;
             break;

         case DW_FORM_block4:
             hash_data_has_fixed_byte_size = false;
             // Fall through to the cases below...
         case DW_FORM_data4:
         case DW_FORM_ref4:
         case DW_FORM_addr:
         case DW_FORM_ref_addr:
         case DW_FORM_strp:
             min_hash_data_byte_size += 4;
             break;

         case DW_FORM_data8:
         case DW_FORM_ref8:
             min_hash_data_byte_size += 8;
             break;

     }
 }

 lldb::offset_t
 DWARFMappedHash::Prologue::Read (const lldb_private::DataExtractor &data,
       lldb::offset_t offset)
 {
     ClearAtoms ();

     die_base_offset = data.GetU32 (&offset);

     const uint32_t atom_count = data.GetU32 (&offset);
     if (atom_count == 0x00060003u)
     {
         // Old format, deal with contents of old pre-release format
         while (data.GetU32(&offset))
             /* do nothing */;

         // Hardcode to the only known value for now.
         AppendAtom (eAtomTypeDIEOffset, DW_FORM_data4);
     }
     else
     {
         for (uint32_t i=0; i<atom_count; ++i)
         {
             AtomType type = (AtomType)data.GetU16 (&offset);
             dw_form_t form = (dw_form_t)data.GetU16 (&offset);
             AppendAtom (type, form);
         }
     }
     return offset;
 }

 size_t
 DWARFMappedHash::Prologue::GetByteSize () const
 {
     // Add an extra count to the atoms size for the zero termination Atom that gets
     // written to disk
     return sizeof(die_base_offset) + sizeof(uint32_t) + atoms.size() * sizeof(Atom);
 }

 size_t
 DWARFMappedHash::Prologue::GetMinimumHashDataByteSize () const
 {
     return min_hash_data_byte_size;
 }

 bool
 DWARFMappedHash::Prologue::HashDataHasFixedByteSize() const
 {
     return hash_data_has_fixed_byte_size;
 }

 size_t
 DWARFMappedHash::Header::GetByteSize (const HeaderData &header_data)
 {
     return header_data.GetByteSize();
 }

 lldb::offset_t
 DWARFMappedHash::Header::Read (lldb_private::DataExtractor &data, lldb::offset_t offset)
 {
     offset = MappedHash::Header<Prologue>::Read (data, offset);
     if (offset != UINT32_MAX)
     {
         offset = header_data.Read (data, offset);
     }
     return offset;
 }

 bool
 DWARFMappedHash::Header::Read (const lldb_private::DWARFDataExtractor &data,
                                lldb::offset_t *offset_ptr,
                                DIEInfo &hash_data) const
 {
     const size_t num_atoms = header_data.atoms.size();
     if (num_atoms == 0)
         return false;

     for (size_t i=0; i<num_atoms; ++i)
     {
         DWARFFormValue form_value (NULL, header_data.atoms[i].form);

         if (!form_value.ExtractValue(data, offset_ptr))
             return false;

         switch (header_data.atoms[i].type)
         {
             case eAtomTypeDIEOffset:    // DIE offset, check form for encoding
                 hash_data.offset = (dw_offset_t)form_value.Reference (header_data.die_base_offset);
                 break;

             case eAtomTypeTag:          // DW_TAG value for the DIE
                 hash_data.tag = (dw_tag_t)form_value.Unsigned ();

             case eAtomTypeTypeFlags:    // Flags from enum TypeFlags
                 hash_data.type_flags = (uint32_t)form_value.Unsigned ();
                 break;

             case eAtomTypeQualNameHash:    // Flags from enum TypeFlags
                 hash_data.qualified_name_hash = form_value.Unsigned ();
                 break;

             default:
                 // We can always skip atoms we don't know about
                 break;
         }
     }
     return true;
 }

 void
 DWARFMappedHash::Header::Dump (lldb_private::Stream& strm, const DIEInfo &hash_data) const
 {
     const size_t num_atoms = header_data.atoms.size();
     for (size_t i=0; i<num_atoms; ++i)
     {
         if (i > 0)
             strm.PutCString (", ");

         DWARFFormValue form_value (NULL, header_data.atoms[i].form);
         switch (header_data.atoms[i].type)
         {
             case eAtomTypeDIEOffset:    // DIE offset, check form for encoding
                 strm.Printf ("{0x%8.8x}", hash_data.offset);
                 break;

             case eAtomTypeTag:          // DW_TAG value for the DIE
                 {
                     const char *tag_cstr = lldb_private::DW_TAG_value_to_name (hash_data.tag);
                     if (tag_cstr)
                         strm.PutCString (tag_cstr);
                     else
                         strm.Printf ("DW_TAG_(0x%4.4x)", hash_data.tag);
                 }
                 break;

             case eAtomTypeTypeFlags:    // Flags from enum TypeFlags
                 strm.Printf ("0x%2.2x", hash_data.type_flags);
                 if (hash_data.type_flags)
                 {
                     strm.PutCString (" (");
                     if (hash_data.type_flags & eTypeFlagClassIsImplementation)
                         strm.PutCString (" implementation");
                     strm.PutCString (" )");
                 }
                 break;

             case eAtomTypeQualNameHash:    // Flags from enum TypeFlags
                 strm.Printf ("0x%8.8x", hash_data.qualified_name_hash);
                 break;

             default:
                 strm.Printf ("AtomType(0x%x)", header_data.atoms[i].type);
                 break;
         }
     }
 }

 DWARFMappedHash::MemoryTable::MemoryTable (lldb_private::DWARFDataExtractor &table_data,
                                            const lldb_private::DWARFDataExtractor &string_table,
                                            const char *name) :
     MappedHash::MemoryTable<uint32_t, Header, DIEInfoArray> (table_data),
     m_data (table_data),
     m_string_table (string_table),
     m_name (name)
 {
 }

 const char *
 DWARFMappedHash::MemoryTable::GetStringForKeyType (KeyType key) const
 {
     // The key in the DWARF table is the .debug_str offset for the string
     return m_string_table.PeekCStr (key);
 }

 bool
 DWARFMappedHash::MemoryTable::ReadHashData (uint32_t hash_data_offset, HashData &hash_data) const
 {
     lldb::offset_t offset = hash_data_offset;
     offset += 4; // Skip string table offset that contains offset of hash name in .debug_str
     const uint32_t count = m_data.GetU32 (&offset);
     if (count > 0)
     {
         hash_data.resize(count);
         for (uint32_t i=0; i<count; ++i)
         {
             if (!m_header.Read(m_data, &offset, hash_data[i]))
                 return false;
         }
     }
     else
         hash_data.clear();
     return true;
 }

 DWARFMappedHash::MemoryTable::Result
 DWARFMappedHash::MemoryTable::GetHashDataForName (const char *name,
                                                   lldb::offset_t* hash_data_offset_ptr,
                                                   Pair &pair) const
 {
     pair.key = m_data.GetU32 (hash_data_offset_ptr);
     pair.value.clear();

     // If the key is zero, this terminates our chain of HashData objects
     // for this hash value.
     if (pair.key == 0)
         return eResultEndOfHashData;

     // There definitely should be a string for this string offset, if
     // there isn't, there is something wrong, return and error
     const char *strp_cstr = m_string_table.PeekCStr (pair.key);
     if (strp_cstr == NULL)
     {
         *hash_data_offset_ptr = UINT32_MAX;
         return eResultError;
     }

     const uint32_t count = m_data.GetU32 (hash_data_offset_ptr);
     const size_t min_total_hash_data_size = count * m_header.header_data.GetMinimumHashDataByteSize();
     if (count > 0 && m_data.ValidOffsetForDataOfSize (*hash_data_offset_ptr, min_total_hash_data_size))
     {
         // We have at least one HashData entry, and we have enough
         // data to parse at least "count" HashData entries.

         // First make sure the entire C string matches...
         const bool match = strcmp (name, strp_cstr) == 0;

         if (!match && m_header.header_data.HashDataHasFixedByteSize())
         {
             // If the string doesn't match and we have fixed size data,
             // we can just add the total byte size of all HashData objects
             // to the hash data offset and be done...
             *hash_data_offset_ptr += min_total_hash_data_size;
         }
         else
         {
             // If the string does match, or we don't have fixed size data
             // then we need to read the hash data as a stream. If the
             // string matches we also append all HashData objects to the
             // value array.
             for (uint32_t i=0; i<count; ++i)
             {
                 DIEInfo die_info;
                 if (m_header.Read(m_data, hash_data_offset_ptr, die_info))
                 {
                     // Only happened if the HashData of the string matched...
                     if (match)
                         pair.value.push_back (die_info);
                 }
                 else
                 {
                     // Something went wrong while reading the data
                     *hash_data_offset_ptr = UINT32_MAX;
                     return eResultError;
                 }
             }
         }
         // Return the correct response depending on if the string matched
         // or not...
         if (match)
             return eResultKeyMatch;     // The key (cstring) matches and we have lookup results!
         else
             return eResultKeyMismatch;  // The key doesn't match, this function will get called
                                         // again for the next key/value or the key terminator
                                         // which in our case is a zero .debug_str offset.
     }
     else
     {
         *hash_data_offset_ptr = UINT32_MAX;
         return eResultError;
     }
 }

 DWARFMappedHash::MemoryTable::Result
 DWARFMappedHash::MemoryTable::AppendHashDataForRegularExpression (
         const lldb_private::RegularExpression& regex,
         lldb::offset_t* hash_data_offset_ptr,
         Pair &pair) const
 {
     pair.key = m_data.GetU32 (hash_data_offset_ptr);
     // If the key is zero, this terminates our chain of HashData objects
     // for this hash value.
     if (pair.key == 0)
         return eResultEndOfHashData;

     // There definitely should be a string for this string offset, if
     // there isn't, there is something wrong, return and error
     const char *strp_cstr = m_string_table.PeekCStr (pair.key);
     if (strp_cstr == NULL)
         return eResultError;

     const uint32_t count = m_data.GetU32 (hash_data_offset_ptr);
     const size_t min_total_hash_data_size = count * m_header.header_data.GetMinimumHashDataByteSize();
     if (count > 0 && m_data.ValidOffsetForDataOfSize (*hash_data_offset_ptr, min_total_hash_data_size))
     {
         const bool match = regex.Execute(strp_cstr);

         if (!match && m_header.header_data.HashDataHasFixedByteSize())
         {
             // If the regex doesn't match and we have fixed size data,
             // we can just add the total byte size of all HashData objects
             // to the hash data offset and be done...
             *hash_data_offset_ptr += min_total_hash_data_size;
         }
         else
         {
             // If the string does match, or we don't have fixed size data
             // then we need to read the hash data as a stream. If the
             // string matches we also append all HashData objects to the
             // value array.
             for (uint32_t i=0; i<count; ++i)
             {
                 DIEInfo die_info;
                 if (m_header.Read(m_data, hash_data_offset_ptr, die_info))
                 {
                     // Only happened if the HashData of the string matched...
                     if (match)
                         pair.value.push_back (die_info);
                 }
                 else
                 {
                     // Something went wrong while reading the data
                     *hash_data_offset_ptr = UINT32_MAX;
                     return eResultError;
                 }
             }
         }
         // Return the correct response depending on if the string matched
         // or not...
         if (match)
             return eResultKeyMatch;     // The key (cstring) matches and we have lookup results!
         else
             return eResultKeyMismatch;  // The key doesn't match, this function will get called
                                         // again for the next key/value or the key terminator
                                         // which in our case is a zero .debug_str offset.
     }
     else
     {
         *hash_data_offset_ptr = UINT32_MAX;
         return eResultError;
     }
 }

 size_t
 DWARFMappedHash::MemoryTable::AppendAllDIEsThatMatchingRegex (
         const lldb_private::RegularExpression& regex,
         DIEInfoArray &die_info_array) const
 {
     const uint32_t hash_count = m_header.hashes_count;
     Pair pair;
     for (uint32_t offset_idx=0; offset_idx<hash_count; ++offset_idx)
     {
         lldb::offset_t hash_data_offset = GetHashDataOffset (offset_idx);
         while (hash_data_offset != UINT32_MAX)
         {
             const lldb::offset_t prev_hash_data_offset = hash_data_offset;
             Result hash_result = AppendHashDataForRegularExpression (regex, &hash_data_offset, pair);
             if (prev_hash_data_offset == hash_data_offset)
                 break;

             // Check the result of getting our hash data
             switch (hash_result)
             {
                 case eResultKeyMatch:
                 case eResultKeyMismatch:
                     // Whether we matches or not, it doesn't matter, we
                     // keep looking.
                     break;

                 case eResultEndOfHashData:
                 case eResultError:
                     hash_data_offset = UINT32_MAX;
                     break;
             }
         }
     }
     die_info_array.swap (pair.value);
     return die_info_array.size();
 }

 size_t
 DWARFMappedHash::MemoryTable::AppendAllDIEsInRange (const uint32_t die_offset_start,
                                                     const uint32_t die_offset_end,
                                                     DIEInfoArray &die_info_array) const
 {
     const uint32_t hash_count = m_header.hashes_count;
     for (uint32_t offset_idx=0; offset_idx<hash_count; ++offset_idx)
     {
         bool done = false;
         lldb::offset_t hash_data_offset = GetHashDataOffset (offset_idx);
         while (!done && hash_data_offset != UINT32_MAX)
         {
             KeyType key = m_data.GetU32 (&hash_data_offset);
             // If the key is zero, this terminates our chain of HashData objects
             // for this hash value.
             if (key == 0)
                 break;

             const uint32_t count = m_data.GetU32 (&hash_data_offset);
             for (uint32_t i=0; i<count; ++i)
             {
                 DIEInfo die_info;
                 if (m_header.Read(m_data, &hash_data_offset, die_info))
                 {
                     if (die_info.offset == 0)
                         done = true;
                     if (die_offset_start <= die_info.offset && die_info.offset < die_offset_end)
                         die_info_array.push_back(die_info);
                 }
             }
         }
     }
     return die_info_array.size();
 }

 size_t
 DWARFMappedHash::MemoryTable::FindByName (const char *name, DIEArray &die_offsets)
 {
     if (!name || !name[0])
         return 0;

     DIEInfoArray die_info_array;
     if (FindByName(name, die_info_array))
         DWARFMappedHash::ExtractDIEArray (die_info_array, die_offsets);
     return die_info_array.size();
 }

 size_t
 DWARFMappedHash::MemoryTable::FindByNameAndTag (const char *name,
                                                 const dw_tag_t tag,
                                                 DIEArray &die_offsets)
 {
     DIEInfoArray die_info_array;
     if (FindByName(name, die_info_array))
         DWARFMappedHash::ExtractDIEArray (die_info_array, tag, die_offsets);
     return die_info_array.size();
 }

 size_t
 DWARFMappedHash::MemoryTable::FindByNameAndTagAndQualifiedNameHash (const char *name,
                                                                     const dw_tag_t tag,
                                                                     const uint32_t qualified_name_hash,
                                                                     DIEArray &die_offsets)
 {
     DIEInfoArray die_info_array;
     if (FindByName(name, die_info_array))
         DWARFMappedHash::ExtractDIEArray (die_info_array, tag, qualified_name_hash, die_offsets);
     return die_info_array.size();
 }

 size_t
 DWARFMappedHash::MemoryTable::FindCompleteObjCClassByName (const char *name,
                                                            DIEArray &die_offsets,
                                                            bool must_be_implementation)
 {
     DIEInfoArray die_info_array;
     if (FindByName(name, die_info_array))
     {
         if (must_be_implementation && GetHeader().header_data.ContainsAtom (eAtomTypeTypeFlags))
         {
             // If we have two atoms, then we have the DIE offset and
             // the type flags so we can find the objective C class
             // efficiently.
             DWARFMappedHash::ExtractTypesFromDIEArray (die_info_array,
                                                        UINT32_MAX,
                                                        eTypeFlagClassIsImplementation,
                                                        die_offsets);
         }
         else
         {
             // We don't only want the one true definition, so try and see
             // what we can find, and only return class or struct DIEs.
             // If we do have the full implementation, then return it alone,
             // else return all possible matches.
             const bool return_implementation_only_if_available = true;
             DWARFMappedHash::ExtractClassOrStructDIEArray (die_info_array,
                                                            return_implementation_only_if_available,
                                                            die_offsets);
         }
     }
     return die_offsets.size();
 }

 size_t
 DWARFMappedHash::MemoryTable::FindByName (const char *name, DIEInfoArray &die_info_array)
 {
     if (!name || !name[0])
         return 0;

     Pair kv_pair;
     size_t old_size = die_info_array.size();
     if (Find (name, kv_pair))
     {
         die_info_array.swap(kv_pair.value);
         return die_info_array.size() - old_size;
     }
     return 0;
 }
	//===-- HashedNameToDIE.cpp -------------------------------------- C++ --===//
	//
	// The LLVM Compiler Infrastructure
	//
	// This file is distributed under the University of Illinois Open Source
	// License. See LICENSE.TXT for details.
	//
	//===----------------------------------------------------------------------===//

	#include "HashedNameToDIE.h"

	void
	DWARFMappedHash::ExtractDIEArray (const DIEInfoArray &die_info_array, DIEArray &die_offsets)
	{
	const size_t count = die_info_array.size();
	for (size_t i=0; i<count; ++i)
	die_offsets.emplace_back(die_info_array[i].cu_offset, die_info_array[i].offset);
	}

	void
	DWARFMappedHash::ExtractDIEArray (const DIEInfoArray &die_info_array,
	const dw_tag_t tag,
	DIEArray &die_offsets)
	{
	if (tag == 0)
	{
	ExtractDIEArray (die_info_array, die_offsets);
	}
	else
	{
	const size_t count = die_info_array.size();
	for (size_t i=0; i<count; ++i)
	{
	const dw_tag_t die_tag = die_info_array[i].tag;
	bool tag_matches = die_tag == 0 \|\| tag == die_tag;
	if (!tag_matches)
	{
	if (die_tag == DW_TAG_class_type \|\| die_tag == DW_TAG_structure_type)
	tag_matches = tag == DW_TAG_structure_type \|\| tag == DW_TAG_class_type;
	}
	if (tag_matches)
	die_offsets.emplace_back(die_info_array[i].cu_offset, die_info_array[i].offset);
	}
	}
	}

	void
	DWARFMappedHash::ExtractDIEArray (const DIEInfoArray &die_info_array,
	const dw_tag_t tag,
	const uint32_t qualified_name_hash,
	DIEArray &die_offsets)
	{
	if (tag == 0)
	{
	ExtractDIEArray (die_info_array, die_offsets);
	}
	else
	{
	const size_t count = die_info_array.size();
	for (size_t i=0; i<count; ++i)
	{
	if (qualified_name_hash != die_info_array[i].qualified_name_hash)
	continue;
	const dw_tag_t die_tag = die_info_array[i].tag;
	bool tag_matches = die_tag == 0 \|\| tag == die_tag;
	if (!tag_matches)
	{
	if (die_tag == DW_TAG_class_type \|\| die_tag == DW_TAG_structure_type)
	tag_matches = tag == DW_TAG_structure_type \|\| tag == DW_TAG_class_type;
	}
	if (tag_matches)
	die_offsets.emplace_back(die_info_array[i].cu_offset, die_info_array[i].offset);
	}
	}
	}

	void
	DWARFMappedHash::ExtractClassOrStructDIEArray (const DIEInfoArray &die_info_array,
	bool return_implementation_only_if_available,
	DIEArray &die_offsets)
	{
	const size_t count = die_info_array.size();
	for (size_t i=0; i<count; ++i)
	{
	const dw_tag_t die_tag = die_info_array[i].tag;
	if (die_tag == 0 \|\| die_tag == DW_TAG_class_type \|\| die_tag == DW_TAG_structure_type)
	{
	if (die_info_array[i].type_flags & eTypeFlagClassIsImplementation)
	{
	if (return_implementation_only_if_available)
	{
	// We found the one true definition for this class, so
	// only return that
	die_offsets.clear();
	die_offsets.emplace_back(die_info_array[i].cu_offset, die_info_array[i].offset);
	return;
	}
	else
	{
	// Put the one true definition as the first entry so it
	// matches first
	die_offsets.emplace(die_offsets.begin(), die_info_array[i].cu_offset, die_info_array[i].offset);
	}
	}
	else
	{
	die_offsets.emplace_back(die_info_array[i].cu_offset, die_info_array[i].offset);
	}
	}
	}
	}

	void
	DWARFMappedHash::ExtractTypesFromDIEArray (const DIEInfoArray &die_info_array,
	uint32_t type_flag_mask,
	uint32_t type_flag_value,
	DIEArray &die_offsets)
	{
	const size_t count = die_info_array.size();
	for (size_t i=0; i<count; ++i)
	{
	if ((die_info_array[i].type_flags & type_flag_mask) == type_flag_value)
	die_offsets.emplace_back(die_info_array[i].cu_offset, die_info_array[i].offset);
	}
	}

	const char *
	DWARFMappedHash::GetAtomTypeName (uint16_t atom)
	{
	switch (atom)
	{
	case eAtomTypeNULL: return "NULL";
	case eAtomTypeDIEOffset: return "die-offset";
	case eAtomTypeCUOffset: return "cu-offset";
	case eAtomTypeTag: return "die-tag";
	case eAtomTypeNameFlags: return "name-flags";
	case eAtomTypeTypeFlags: return "type-flags";
	case eAtomTypeQualNameHash: return "qualified-name-hash";
	}
	return "<invalid>";
	}

	DWARFMappedHash::DIEInfo::DIEInfo () :
	cu_offset (DW_INVALID_OFFSET),
	offset (DW_INVALID_OFFSET),
	tag (0),
	type_flags (0),
	qualified_name_hash (0)
	{
	}

	DWARFMappedHash::DIEInfo::DIEInfo (dw_offset_t c,
	dw_offset_t o,
	dw_tag_t t,
	uint32_t f,
	uint32_t h) :
	cu_offset (c),
	offset (o),
	tag (t),
	type_flags (f),
	qualified_name_hash (h)
	{
	}

	DWARFMappedHash::Prologue::Prologue (dw_offset_t _die_base_offset) :
	die_base_offset (_die_base_offset),
	atoms(),
	atom_mask (0),
	min_hash_data_byte_size(0),
	hash_data_has_fixed_byte_size(true)
	{
	// Define an array of DIE offsets by first defining an array,
	// and then define the atom type for the array, in this case
	// we have an array of DIE offsets
	AppendAtom (eAtomTypeDIEOffset, DW_FORM_data4);
	}

	void
	DWARFMappedHash::Prologue::ClearAtoms ()
	{
	hash_data_has_fixed_byte_size = true;
	min_hash_data_byte_size = 0;
	atom_mask = 0;
	atoms.clear();
	}

	bool
	DWARFMappedHash::Prologue::ContainsAtom (AtomType atom_type) const
	{
	return (atom_mask & (1u << atom_type)) != 0;
	}

	void
	DWARFMappedHash::Prologue::Clear ()
	{
	die_base_offset = 0;
	ClearAtoms ();
	}

	void
	DWARFMappedHash::Prologue::AppendAtom (AtomType type, dw_form_t form)
	{
	atoms.push_back ({type, form});
	atom_mask \|= 1u << type;
	switch (form)
	{
	case DW_FORM_indirect:
	case DW_FORM_exprloc:
	case DW_FORM_flag_present:
	case DW_FORM_ref_sig8:
	assert (!"Unhandled atom form");
	break;

	case DW_FORM_string:
	case DW_FORM_block:
	case DW_FORM_block1:
	case DW_FORM_sdata:
	case DW_FORM_udata:
	case DW_FORM_ref_udata:
	case DW_FORM_GNU_addr_index:
	case DW_FORM_GNU_str_index:
	hash_data_has_fixed_byte_size = false;
	// Fall through to the cases below...
	case DW_FORM_flag:
	case DW_FORM_data1:
	case DW_FORM_ref1:
	case DW_FORM_sec_offset:
	min_hash_data_byte_size += 1;
	break;

	case DW_FORM_block2:
	hash_data_has_fixed_byte_size = false;
	// Fall through to the cases below...
	case DW_FORM_data2:
	case DW_FORM_ref2:
	min_hash_data_byte_size += 2;
	break;

	case DW_FORM_block4:
	hash_data_has_fixed_byte_size = false;
	// Fall through to the cases below...
	case DW_FORM_data4:
	case DW_FORM_ref4:
	case DW_FORM_addr:
	case DW_FORM_ref_addr:
	case DW_FORM_strp:
	min_hash_data_byte_size += 4;
	break;

	case DW_FORM_data8:
	case DW_FORM_ref8:
	min_hash_data_byte_size += 8;
	break;

	}
	}

	lldb::offset_t
	DWARFMappedHash::Prologue::Read (const lldb_private::DataExtractor &data,
	lldb::offset_t offset)
	{
	ClearAtoms ();

	die_base_offset = data.GetU32 (&offset);

	const uint32_t atom_count = data.GetU32 (&offset);
	if (atom_count == 0x00060003u)
	{
	// Old format, deal with contents of old pre-release format
	while (data.GetU32(&offset))
	/* do nothing */;

	// Hardcode to the only known value for now.
	AppendAtom (eAtomTypeDIEOffset, DW_FORM_data4);
	}
	else
	{
	for (uint32_t i=0; i<atom_count; ++i)
	{
	AtomType type = (AtomType)data.GetU16 (&offset);
	dw_form_t form = (dw_form_t)data.GetU16 (&offset);
	AppendAtom (type, form);
	}
	}
	return offset;
	}

	size_t
	DWARFMappedHash::Prologue::GetByteSize () const
	{
	// Add an extra count to the atoms size for the zero termination Atom that gets
	// written to disk
	return sizeof(die_base_offset) + sizeof(uint32_t) + atoms.size() * sizeof(Atom);
	}

	size_t
	DWARFMappedHash::Prologue::GetMinimumHashDataByteSize () const
	{
	return min_hash_data_byte_size;
	}

	bool
	DWARFMappedHash::Prologue::HashDataHasFixedByteSize() const
	{
	return hash_data_has_fixed_byte_size;
	}

	size_t
	DWARFMappedHash::Header::GetByteSize (const HeaderData &header_data)
	{
	return header_data.GetByteSize();
	}

	lldb::offset_t
	DWARFMappedHash::Header::Read (lldb_private::DataExtractor &data, lldb::offset_t offset)
	{
	offset = MappedHash::Header<Prologue>::Read (data, offset);
	if (offset != UINT32_MAX)
	{
	offset = header_data.Read (data, offset);
	}
	return offset;
	}

	bool
	DWARFMappedHash::Header::Read (const lldb_private::DWARFDataExtractor &data,
	lldb::offset_t *offset_ptr,
	DIEInfo &hash_data) const
	{
	const size_t num_atoms = header_data.atoms.size();
	if (num_atoms == 0)
	return false;

	for (size_t i=0; i<num_atoms; ++i)
	{
	DWARFFormValue form_value (NULL, header_data.atoms[i].form);

	if (!form_value.ExtractValue(data, offset_ptr))
	return false;

	switch (header_data.atoms[i].type)
	{
	case eAtomTypeDIEOffset: // DIE offset, check form for encoding
	hash_data.offset = (dw_offset_t)form_value.Reference (header_data.die_base_offset);
	break;

	case eAtomTypeTag: // DW_TAG value for the DIE
	hash_data.tag = (dw_tag_t)form_value.Unsigned ();

	case eAtomTypeTypeFlags: // Flags from enum TypeFlags
	hash_data.type_flags = (uint32_t)form_value.Unsigned ();
	break;

	case eAtomTypeQualNameHash: // Flags from enum TypeFlags
	hash_data.qualified_name_hash = form_value.Unsigned ();
	break;

	default:
	// We can always skip atoms we don't know about
	break;
	}
	}
	return true;
	}

	void
	DWARFMappedHash::Header::Dump (lldb_private::Stream& strm, const DIEInfo &hash_data) const
	{
	const size_t num_atoms = header_data.atoms.size();
	for (size_t i=0; i<num_atoms; ++i)
	{
	if (i > 0)
	strm.PutCString (", ");

	DWARFFormValue form_value (NULL, header_data.atoms[i].form);
	switch (header_data.atoms[i].type)
	{
	case eAtomTypeDIEOffset: // DIE offset, check form for encoding
	strm.Printf ("{0x%8.8x}", hash_data.offset);
	break;

	case eAtomTypeTag: // DW_TAG value for the DIE
	{
	const char *tag_cstr = lldb_private::DW_TAG_value_to_name (hash_data.tag);
	if (tag_cstr)
	strm.PutCString (tag_cstr);
	else
	strm.Printf ("DW_TAG_(0x%4.4x)", hash_data.tag);
	}
	break;

	case eAtomTypeTypeFlags: // Flags from enum TypeFlags
	strm.Printf ("0x%2.2x", hash_data.type_flags);
	if (hash_data.type_flags)
	{
	strm.PutCString (" (");
	if (hash_data.type_flags & eTypeFlagClassIsImplementation)
	strm.PutCString (" implementation");
	strm.PutCString (" )");
	}
	break;

	case eAtomTypeQualNameHash: // Flags from enum TypeFlags
	strm.Printf ("0x%8.8x", hash_data.qualified_name_hash);
	break;

	default:
	strm.Printf ("AtomType(0x%x)", header_data.atoms[i].type);
	break;
	}
	}
	}

	DWARFMappedHash::MemoryTable::MemoryTable (lldb_private::DWARFDataExtractor &table_data,
	const lldb_private::DWARFDataExtractor &string_table,
	const char *name) :
	MappedHash::MemoryTable<uint32_t, Header, DIEInfoArray> (table_data),
	m_data (table_data),
	m_string_table (string_table),
	m_name (name)
	{
	}

	const char *
	DWARFMappedHash::MemoryTable::GetStringForKeyType (KeyType key) const
	{
	// The key in the DWARF table is the .debug_str offset for the string
	return m_string_table.PeekCStr (key);
	}

	bool
	DWARFMappedHash::MemoryTable::ReadHashData (uint32_t hash_data_offset, HashData &hash_data) const
	{
	lldb::offset_t offset = hash_data_offset;
	offset += 4; // Skip string table offset that contains offset of hash name in .debug_str
	const uint32_t count = m_data.GetU32 (&offset);
	if (count > 0)
	{
	hash_data.resize(count);
	for (uint32_t i=0; i<count; ++i)
	{
	if (!m_header.Read(m_data, &offset, hash_data[i]))
	return false;
	}
	}
	else
	hash_data.clear();
	return true;
	}

	DWARFMappedHash::MemoryTable::Result
	DWARFMappedHash::MemoryTable::GetHashDataForName (const char *name,
	lldb::offset_t* hash_data_offset_ptr,
	Pair &pair) const
	{
	pair.key = m_data.GetU32 (hash_data_offset_ptr);
	pair.value.clear();

	// If the key is zero, this terminates our chain of HashData objects
	// for this hash value.
	if (pair.key == 0)
	return eResultEndOfHashData;

	// There definitely should be a string for this string offset, if
	// there isn't, there is something wrong, return and error
	const char *strp_cstr = m_string_table.PeekCStr (pair.key);
	if (strp_cstr == NULL)
	{
	*hash_data_offset_ptr = UINT32_MAX;
	return eResultError;
	}

	const uint32_t count = m_data.GetU32 (hash_data_offset_ptr);
	const size_t min_total_hash_data_size = count * m_header.header_data.GetMinimumHashDataByteSize();
	if (count > 0 && m_data.ValidOffsetForDataOfSize (*hash_data_offset_ptr, min_total_hash_data_size))
	{
	// We have at least one HashData entry, and we have enough
	// data to parse at least "count" HashData entries.

	// First make sure the entire C string matches...
	const bool match = strcmp (name, strp_cstr) == 0;

	if (!match && m_header.header_data.HashDataHasFixedByteSize())
	{
	// If the string doesn't match and we have fixed size data,
	// we can just add the total byte size of all HashData objects
	// to the hash data offset and be done...
	*hash_data_offset_ptr += min_total_hash_data_size;
	}
	else
	{
	// If the string does match, or we don't have fixed size data
	// then we need to read the hash data as a stream. If the
	// string matches we also append all HashData objects to the
	// value array.
	for (uint32_t i=0; i<count; ++i)
	{
	DIEInfo die_info;
	if (m_header.Read(m_data, hash_data_offset_ptr, die_info))
	{
	// Only happened if the HashData of the string matched...
	if (match)
	pair.value.push_back (die_info);
	}
	else
	{
	// Something went wrong while reading the data
	*hash_data_offset_ptr = UINT32_MAX;
	return eResultError;
	}
	}
	}
	// Return the correct response depending on if the string matched
	// or not...
	if (match)
	return eResultKeyMatch; // The key (cstring) matches and we have lookup results!
	else
	return eResultKeyMismatch; // The key doesn't match, this function will get called
	// again for the next key/value or the key terminator
	// which in our case is a zero .debug_str offset.
	}
	else
	{
	*hash_data_offset_ptr = UINT32_MAX;
	return eResultError;
	}
	}

	DWARFMappedHash::MemoryTable::Result
	DWARFMappedHash::MemoryTable::AppendHashDataForRegularExpression (
	const lldb_private::RegularExpression& regex,
	lldb::offset_t* hash_data_offset_ptr,
	Pair &pair) const
	{
	pair.key = m_data.GetU32 (hash_data_offset_ptr);
	// If the key is zero, this terminates our chain of HashData objects
	// for this hash value.
	if (pair.key == 0)
	return eResultEndOfHashData;

	// There definitely should be a string for this string offset, if
	// there isn't, there is something wrong, return and error
	const char *strp_cstr = m_string_table.PeekCStr (pair.key);
	if (strp_cstr == NULL)
	return eResultError;

	const uint32_t count = m_data.GetU32 (hash_data_offset_ptr);
	const size_t min_total_hash_data_size = count * m_header.header_data.GetMinimumHashDataByteSize();
	if (count > 0 && m_data.ValidOffsetForDataOfSize (*hash_data_offset_ptr, min_total_hash_data_size))
	{
	const bool match = regex.Execute(strp_cstr);

	if (!match && m_header.header_data.HashDataHasFixedByteSize())
	{
	// If the regex doesn't match and we have fixed size data,
	// we can just add the total byte size of all HashData objects
	// to the hash data offset and be done...
	*hash_data_offset_ptr += min_total_hash_data_size;
	}
	else
	{
	// If the string does match, or we don't have fixed size data
	// then we need to read the hash data as a stream. If the
	// string matches we also append all HashData objects to the
	// value array.
	for (uint32_t i=0; i<count; ++i)
	{
	DIEInfo die_info;
	if (m_header.Read(m_data, hash_data_offset_ptr, die_info))
	{
	// Only happened if the HashData of the string matched...
	if (match)
	pair.value.push_back (die_info);
	}
	else
	{
	// Something went wrong while reading the data
	*hash_data_offset_ptr = UINT32_MAX;
	return eResultError;
	}
	}
	}
	// Return the correct response depending on if the string matched
	// or not...
	if (match)
	return eResultKeyMatch; // The key (cstring) matches and we have lookup results!
	else
	return eResultKeyMismatch; // The key doesn't match, this function will get called
	// again for the next key/value or the key terminator
	// which in our case is a zero .debug_str offset.
	}
	else
	{
	*hash_data_offset_ptr = UINT32_MAX;
	return eResultError;
	}
	}

	size_t
	DWARFMappedHash::MemoryTable::AppendAllDIEsThatMatchingRegex (
	const lldb_private::RegularExpression& regex,
	DIEInfoArray &die_info_array) const
	{
	const uint32_t hash_count = m_header.hashes_count;
	Pair pair;
	for (uint32_t offset_idx=0; offset_idx<hash_count; ++offset_idx)
	{
	lldb::offset_t hash_data_offset = GetHashDataOffset (offset_idx);
	while (hash_data_offset != UINT32_MAX)
	{
	const lldb::offset_t prev_hash_data_offset = hash_data_offset;
	Result hash_result = AppendHashDataForRegularExpression (regex, &hash_data_offset, pair);
	if (prev_hash_data_offset == hash_data_offset)
	break;

	// Check the result of getting our hash data
	switch (hash_result)
	{
	case eResultKeyMatch:
	case eResultKeyMismatch:
	// Whether we matches or not, it doesn't matter, we
	// keep looking.
	break;

	case eResultEndOfHashData:
	case eResultError:
	hash_data_offset = UINT32_MAX;
	break;
	}
	}
	}
	die_info_array.swap (pair.value);
	return die_info_array.size();
	}

	size_t
	DWARFMappedHash::MemoryTable::AppendAllDIEsInRange (const uint32_t die_offset_start,
	const uint32_t die_offset_end,
	DIEInfoArray &die_info_array) const
	{
	const uint32_t hash_count = m_header.hashes_count;
	for (uint32_t offset_idx=0; offset_idx<hash_count; ++offset_idx)
	{
	bool done = false;
	lldb::offset_t hash_data_offset = GetHashDataOffset (offset_idx);
	while (!done && hash_data_offset != UINT32_MAX)
	{
	KeyType key = m_data.GetU32 (&hash_data_offset);
	// If the key is zero, this terminates our chain of HashData objects
	// for this hash value.
	if (key == 0)
	break;

	const uint32_t count = m_data.GetU32 (&hash_data_offset);
	for (uint32_t i=0; i<count; ++i)
	{
	DIEInfo die_info;
	if (m_header.Read(m_data, &hash_data_offset, die_info))
	{
	if (die_info.offset == 0)
	done = true;
	if (die_offset_start <= die_info.offset && die_info.offset < die_offset_end)
	die_info_array.push_back(die_info);
	}
	}
	}
	}
	return die_info_array.size();
	}

	size_t
	DWARFMappedHash::MemoryTable::FindByName (const char *name, DIEArray &die_offsets)
	{
	if (!name \|\| !name[0])
	return 0;

	DIEInfoArray die_info_array;
	if (FindByName(name, die_info_array))
	DWARFMappedHash::ExtractDIEArray (die_info_array, die_offsets);
	return die_info_array.size();
	}

	size_t
	DWARFMappedHash::MemoryTable::FindByNameAndTag (const char *name,
	const dw_tag_t tag,
	DIEArray &die_offsets)
	{
	DIEInfoArray die_info_array;
	if (FindByName(name, die_info_array))
	DWARFMappedHash::ExtractDIEArray (die_info_array, tag, die_offsets);
	return die_info_array.size();
	}

	size_t
	DWARFMappedHash::MemoryTable::FindByNameAndTagAndQualifiedNameHash (const char *name,
	const dw_tag_t tag,
	const uint32_t qualified_name_hash,
	DIEArray &die_offsets)
	{
	DIEInfoArray die_info_array;
	if (FindByName(name, die_info_array))
	DWARFMappedHash::ExtractDIEArray (die_info_array, tag, qualified_name_hash, die_offsets);
	return die_info_array.size();
	}

	size_t
	DWARFMappedHash::MemoryTable::FindCompleteObjCClassByName (const char *name,
	DIEArray &die_offsets,
	bool must_be_implementation)
	{
	DIEInfoArray die_info_array;
	if (FindByName(name, die_info_array))
	{
	if (must_be_implementation && GetHeader().header_data.ContainsAtom (eAtomTypeTypeFlags))
	{
	// If we have two atoms, then we have the DIE offset and
	// the type flags so we can find the objective C class
	// efficiently.
	DWARFMappedHash::ExtractTypesFromDIEArray (die_info_array,
	UINT32_MAX,
	eTypeFlagClassIsImplementation,
	die_offsets);
	}
	else
	{
	// We don't only want the one true definition, so try and see
	// what we can find, and only return class or struct DIEs.
	// If we do have the full implementation, then return it alone,
	// else return all possible matches.
	const bool return_implementation_only_if_available = true;
	DWARFMappedHash::ExtractClassOrStructDIEArray (die_info_array,
	return_implementation_only_if_available,
	die_offsets);
	}
	}
	return die_offsets.size();
	}

	size_t
	DWARFMappedHash::MemoryTable::FindByName (const char *name, DIEInfoArray &die_info_array)
	{
	if (!name \|\| !name[0])
	return 0;

	Pair kv_pair;
	size_t old_size = die_info_array.size();
	if (Find (name, kv_pair))
	{
	die_info_array.swap(kv_pair.value);
	return die_info_array.size() - old_size;
	}
	return 0;
	}