llvm/lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp

   1 //===- DWARFAcceleratorTable.cpp ------------------------------------------===//
   2 //
   3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
   4 // See https://llvm.org/LICENSE.txt for license information.
   5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
   6 //
   7 //===----------------------------------------------------------------------===//
   8
   9 #include "llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h"
  10
  11 #include "llvm/ADT/SmallVector.h"
  12 #include "llvm/BinaryFormat/Dwarf.h"
  13 #include "llvm/Support/Compiler.h"
  14 #include "llvm/Support/DJB.h"
  15 #include "llvm/Support/Errc.h"
  16 #include "llvm/Support/Format.h"
  17 #include "llvm/Support/FormatVariadic.h"
  18 #include "llvm/Support/ScopedPrinter.h"
  19 #include "llvm/Support/raw_ostream.h"
  20 #include <cstddef>
  21 #include <cstdint>
  22 #include <utility>
  23
  24 using namespace llvm;
  25
  26 namespace {
  27 struct Atom {
  28   unsigned Value;
  29 };
  30
  31 static raw_ostream &operator<<(raw_ostream &OS, const Atom &A) {
  32   StringRef Str = dwarf::AtomTypeString(A.Value);
  33   if (!Str.empty())
  34     return OS << Str;
  35   return OS << "DW_ATOM_unknown_" << format("%x", A.Value);
  36 }
  37 } // namespace
  38
  39 static Atom formatAtom(unsigned Atom) { return {Atom}; }
  40
  41 DWARFAcceleratorTable::~DWARFAcceleratorTable() = default;
  42
  43 Error AppleAcceleratorTable::extract() {
  44   uint64_t Offset = 0;
  45
  46   // Check that we can at least read the header.
  47   if (!AccelSection.isValidOffset(offsetof(Header, HeaderDataLength) + 4))
  48     return createStringError(errc::illegal_byte_sequence,
  49                              "Section too small: cannot read header.");
  50
  51   Hdr.Magic = AccelSection.getU32(&Offset);
  52   Hdr.Version = AccelSection.getU16(&Offset);
  53   Hdr.HashFunction = AccelSection.getU16(&Offset);
  54   Hdr.BucketCount = AccelSection.getU32(&Offset);
  55   Hdr.HashCount = AccelSection.getU32(&Offset);
  56   Hdr.HeaderDataLength = AccelSection.getU32(&Offset);
  57   FormParams = {Hdr.Version, 0, dwarf::DwarfFormat::DWARF32};
  58
  59   // Check that we can read all the hashes and offsets from the
  60   // section (see SourceLevelDebugging.rst for the structure of the index).
  61   if (!AccelSection.isValidOffset(getIthBucketBase(Hdr.BucketCount - 1)))
  62     return createStringError(
  63         errc::illegal_byte_sequence,
  64         "Section too small: cannot read buckets and hashes.");
  65
  66   HdrData.DIEOffsetBase = AccelSection.getU32(&Offset);
  67   uint32_t NumAtoms = AccelSection.getU32(&Offset);
  68
  69   HashDataEntryLength = 0;
  70   auto MakeUnsupportedFormError = [](dwarf::Form Form) {
  71     return createStringError(errc::not_supported,
  72                              "Unsupported form:" +
  73                                  dwarf::FormEncodingString(Form));
  74   };
  75
  76   for (unsigned i = 0; i < NumAtoms; ++i) {
  77     uint16_t AtomType = AccelSection.getU16(&Offset);
  78     auto AtomForm = static_cast<dwarf::Form>(AccelSection.getU16(&Offset));
  79     HdrData.Atoms.push_back(std::make_pair(AtomType, AtomForm));
  80
  81     std::optional<uint8_t> FormSize =
  82         dwarf::getFixedFormByteSize(AtomForm, FormParams);
  83     if (!FormSize)
  84       return MakeUnsupportedFormError(AtomForm);
  85     HashDataEntryLength += *FormSize;
  86   }
  87
  88   IsValid = true;
  89   return Error::success();
  90 }
  91
  92 uint32_t AppleAcceleratorTable::getNumBuckets() const {
  93   return Hdr.BucketCount;
  94 }
  95 uint32_t AppleAcceleratorTable::getNumHashes() const { return Hdr.HashCount; }
  96 uint32_t AppleAcceleratorTable::getSizeHdr() const { return sizeof(Hdr); }
  97 uint32_t AppleAcceleratorTable::getHeaderDataLength() const {
  98   return Hdr.HeaderDataLength;
  99 }
 100
 101 ArrayRef<std::pair<AppleAcceleratorTable::HeaderData::AtomType,
 102                    AppleAcceleratorTable::HeaderData::Form>>
 103 AppleAcceleratorTable::getAtomsDesc() {
 104   return HdrData.Atoms;
 105 }
 106
 107 bool AppleAcceleratorTable::validateForms() {
 108   for (auto Atom : getAtomsDesc()) {
 109     DWARFFormValue FormValue(Atom.second);
 110     switch (Atom.first) {
 111     case dwarf::DW_ATOM_die_offset:
 112     case dwarf::DW_ATOM_die_tag:
 113     case dwarf::DW_ATOM_type_flags:
 114       if ((!FormValue.isFormClass(DWARFFormValue::FC_Constant) &&
 115            !FormValue.isFormClass(DWARFFormValue::FC_Flag)) ||
 116           FormValue.getForm() == dwarf::DW_FORM_sdata)
 117         return false;
 118       break;
 119     default:
 120       break;
 121     }
 122   }
 123   return true;
 124 }
 125
 126 std::pair<uint64_t, dwarf::Tag>
 127 AppleAcceleratorTable::readAtoms(uint64_t *HashDataOffset) {
 128   uint64_t DieOffset = dwarf::DW_INVALID_OFFSET;
 129   dwarf::Tag DieTag = dwarf::DW_TAG_null;
 130
 131   for (auto Atom : getAtomsDesc()) {
 132     DWARFFormValue FormValue(Atom.second);
 133     FormValue.extractValue(AccelSection, HashDataOffset, FormParams);
 134     switch (Atom.first) {
 135     case dwarf::DW_ATOM_die_offset:
 136       DieOffset = *FormValue.getAsUnsignedConstant();
 137       break;
 138     case dwarf::DW_ATOM_die_tag:
 139       DieTag = (dwarf::Tag)*FormValue.getAsUnsignedConstant();
 140       break;
 141     default:
 142       break;
 143     }
 144   }
 145   return {DieOffset, DieTag};
 146 }
 147
 148 void AppleAcceleratorTable::Header::dump(ScopedPrinter &W) const {
 149   DictScope HeaderScope(W, "Header");
 150   W.printHex("Magic", Magic);
 151   W.printHex("Version", Version);
 152   W.printHex("Hash function", HashFunction);
 153   W.printNumber("Bucket count", BucketCount);
 154   W.printNumber("Hashes count", HashCount);
 155   W.printNumber("HeaderData length", HeaderDataLength);
 156 }
 157
 158 std::optional<uint64_t> AppleAcceleratorTable::HeaderData::extractOffset(
 159     std::optional<DWARFFormValue> Value) const {
 160   if (!Value)
 161     return std::nullopt;
 162
 163   switch (Value->getForm()) {
 164   case dwarf::DW_FORM_ref1:
 165   case dwarf::DW_FORM_ref2:
 166   case dwarf::DW_FORM_ref4:
 167   case dwarf::DW_FORM_ref8:
 168   case dwarf::DW_FORM_ref_udata:
 169     return Value->getRawUValue() + DIEOffsetBase;
 170   default:
 171     return Value->getAsSectionOffset();
 172   }
 173 }
 174
 175 bool AppleAcceleratorTable::dumpName(ScopedPrinter &W,
 176                                      SmallVectorImpl<DWARFFormValue> &AtomForms,
 177                                      uint64_t *DataOffset) const {
 178   uint64_t NameOffset = *DataOffset;
 179   if (!AccelSection.isValidOffsetForDataOfSize(*DataOffset, 4)) {
 180     W.printString("Incorrectly terminated list.");
 181     return false;
 182   }
 183   uint64_t StringOffset = AccelSection.getRelocatedValue(4, DataOffset);
 184   if (!StringOffset)
 185     return false; // End of list
 186
 187   DictScope NameScope(W, ("Name@0x" + Twine::utohexstr(NameOffset)).str());
 188   W.startLine() << format("String: 0x%08" PRIx64, StringOffset);
 189   W.getOStream() << " \"" << StringSection.getCStr(&StringOffset) << "\"\n";
 190
 191   unsigned NumData = AccelSection.getU32(DataOffset);
 192   for (unsigned Data = 0; Data < NumData; ++Data) {
 193     ListScope DataScope(W, ("Data " + Twine(Data)).str());
 194     unsigned i = 0;
 195     for (auto &Atom : AtomForms) {
 196       W.startLine() << format("Atom[%d]: ", i);
 197       if (Atom.extractValue(AccelSection, DataOffset, FormParams)) {
 198         Atom.dump(W.getOStream());
 199         if (std::optional<uint64_t> Val = Atom.getAsUnsignedConstant()) {
 200           StringRef Str = dwarf::AtomValueString(HdrData.Atoms[i].first, *Val);
 201           if (!Str.empty())
 202             W.getOStream() << " (" << Str << ")";
 203         }
 204       } else
 205         W.getOStream() << "Error extracting the value";
 206       W.getOStream() << "\n";
 207       i++;
 208     }
 209   }
 210   return true; // more entries follow
 211 }
 212
 213 LLVM_DUMP_METHOD void AppleAcceleratorTable::dump(raw_ostream &OS) const {
 214   if (!IsValid)
 215     return;
 216
 217   ScopedPrinter W(OS);
 218
 219   Hdr.dump(W);
 220
 221   W.printNumber("DIE offset base", HdrData.DIEOffsetBase);
 222   W.printNumber("Number of atoms", uint64_t(HdrData.Atoms.size()));
 223   W.printNumber("Size of each hash data entry", getHashDataEntryLength());
 224   SmallVector<DWARFFormValue, 3> AtomForms;
 225   {
 226     ListScope AtomsScope(W, "Atoms");
 227     unsigned i = 0;
 228     for (const auto &Atom : HdrData.Atoms) {
 229       DictScope AtomScope(W, ("Atom " + Twine(i++)).str());
 230       W.startLine() << "Type: " << formatAtom(Atom.first) << '\n';
 231       W.startLine() << "Form: " << formatv("{0}", Atom.second) << '\n';
 232       AtomForms.push_back(DWARFFormValue(Atom.second));
 233     }
 234   }
 235
 236   // Now go through the actual tables and dump them.
 237   uint64_t Offset = sizeof(Hdr) + Hdr.HeaderDataLength;
 238   uint64_t HashesBase = Offset + Hdr.BucketCount * 4;
 239   uint64_t OffsetsBase = HashesBase + Hdr.HashCount * 4;
 240
 241   for (unsigned Bucket = 0; Bucket < Hdr.BucketCount; ++Bucket) {
 242     unsigned Index = AccelSection.getU32(&Offset);
 243
 244     ListScope BucketScope(W, ("Bucket " + Twine(Bucket)).str());
 245     if (Index == UINT32_MAX) {
 246       W.printString("EMPTY");
 247       continue;
 248     }
 249
 250     for (unsigned HashIdx = Index; HashIdx < Hdr.HashCount; ++HashIdx) {
 251       uint64_t HashOffset = HashesBase + HashIdx*4;
 252       uint64_t OffsetsOffset = OffsetsBase + HashIdx*4;
 253       uint32_t Hash = AccelSection.getU32(&HashOffset);
 254
 255       if (Hash % Hdr.BucketCount != Bucket)
 256         break;
 257
 258       uint64_t DataOffset = AccelSection.getU32(&OffsetsOffset);
 259       ListScope HashScope(W, ("Hash 0x" + Twine::utohexstr(Hash)).str());
 260       if (!AccelSection.isValidOffset(DataOffset)) {
 261         W.printString("Invalid section offset");
 262         continue;
 263       }
 264       while (dumpName(W, AtomForms, &DataOffset))
 265         /*empty*/;
 266     }
 267   }
 268 }
 269
 270 AppleAcceleratorTable::Entry::Entry(const AppleAcceleratorTable &Table)
 271     : Table(Table) {
 272   Values.reserve(Table.HdrData.Atoms.size());
 273   for (const auto &Atom : Table.HdrData.Atoms)
 274     Values.push_back(DWARFFormValue(Atom.second));
 275 }
 276
 277 void AppleAcceleratorTable::Entry::extract(uint64_t *Offset) {
 278   for (auto &FormValue : Values)
 279     FormValue.extractValue(Table.AccelSection, Offset, Table.FormParams);
 280 }
 281
 282 std::optional<DWARFFormValue>
 283 AppleAcceleratorTable::Entry::lookup(HeaderData::AtomType AtomToFind) const {
 284   for (auto [Atom, FormValue] : zip_equal(Table.HdrData.Atoms, Values))
 285     if (Atom.first == AtomToFind)
 286       return FormValue;
 287   return std::nullopt;
 288 }
 289
 290 std::optional<uint64_t>
 291 AppleAcceleratorTable::Entry::getDIESectionOffset() const {
 292   return Table.HdrData.extractOffset(lookup(dwarf::DW_ATOM_die_offset));
 293 }
 294
 295 std::optional<uint64_t> AppleAcceleratorTable::Entry::getCUOffset() const {
 296   return Table.HdrData.extractOffset(lookup(dwarf::DW_ATOM_cu_offset));
 297 }
 298
 299 std::optional<dwarf::Tag> AppleAcceleratorTable::Entry::getTag() const {
 300   std::optional<DWARFFormValue> Tag = lookup(dwarf::DW_ATOM_die_tag);
 301   if (!Tag)
 302     return std::nullopt;
 303   if (std::optional<uint64_t> Value = Tag->getAsUnsignedConstant())
 304     return dwarf::Tag(*Value);
 305   return std::nullopt;
 306 }
 307
 308 AppleAcceleratorTable::SameNameIterator::SameNameIterator(
 309     const AppleAcceleratorTable &AccelTable, uint64_t DataOffset)
 310     : Current(AccelTable), Offset(DataOffset) {}
 311
 312 void AppleAcceleratorTable::Iterator::prepareNextEntryOrEnd() {
 313   if (NumEntriesToCome == 0)
 314     prepareNextStringOrEnd();
 315   if (isEnd())
 316     return;
 317   uint64_t OffsetCopy = Offset;
 318   Current.BaseEntry.extract(&OffsetCopy);
 319   NumEntriesToCome--;
 320   Offset += getTable().getHashDataEntryLength();
 321 }
 322
 323 void AppleAcceleratorTable::Iterator::prepareNextStringOrEnd() {
 324   std::optional<uint32_t> StrOffset = getTable().readStringOffsetAt(Offset);
 325   if (!StrOffset)
 326     return setToEnd();
 327
 328   // A zero denotes the end of the collision list. Read the next string
 329   // again.
 330   if (*StrOffset == 0)
 331     return prepareNextStringOrEnd();
 332   Current.StrOffset = *StrOffset;
 333
 334   std::optional<uint32_t> MaybeNumEntries = getTable().readU32FromAccel(Offset);
 335   if (!MaybeNumEntries || *MaybeNumEntries == 0)
 336     return setToEnd();
 337   NumEntriesToCome = *MaybeNumEntries;
 338 }
 339
 340 AppleAcceleratorTable::Iterator::Iterator(const AppleAcceleratorTable &Table,
 341                                           bool SetEnd)
 342     : Current(Table), Offset(Table.getEntriesBase()), NumEntriesToCome(0) {
 343   if (SetEnd)
 344     setToEnd();
 345   else
 346     prepareNextEntryOrEnd();
 347 }
 348
 349 iterator_range<AppleAcceleratorTable::SameNameIterator>
 350 AppleAcceleratorTable::equal_range(StringRef Key) const {
 351   const auto EmptyRange =
 352       make_range(SameNameIterator(*this, 0), SameNameIterator(*this, 0));
 353   if (!IsValid)
 354     return EmptyRange;
 355
 356   // Find the bucket.
 357   uint32_t SearchHash = djbHash(Key);
 358   uint32_t BucketIdx = hashToBucketIdx(SearchHash);
 359   std::optional<uint32_t> HashIdx = idxOfHashInBucket(SearchHash, BucketIdx);
 360   if (!HashIdx)
 361     return EmptyRange;
 362
 363   std::optional<uint64_t> MaybeDataOffset = readIthOffset(*HashIdx);
 364   if (!MaybeDataOffset)
 365     return EmptyRange;
 366
 367   uint64_t DataOffset = *MaybeDataOffset;
 368   if (DataOffset >= AccelSection.size())
 369     return EmptyRange;
 370
 371   std::optional<uint32_t> StrOffset = readStringOffsetAt(DataOffset);
 372   // Valid input and still have strings in this hash.
 373   while (StrOffset && *StrOffset) {
 374     std::optional<StringRef> MaybeStr = readStringFromStrSection(*StrOffset);
 375     std::optional<uint32_t> NumEntries = this->readU32FromAccel(DataOffset);
 376     if (!MaybeStr || !NumEntries)
 377       return EmptyRange;
 378     uint64_t EndOffset = DataOffset + *NumEntries * getHashDataEntryLength();
 379     if (Key == *MaybeStr)
 380       return make_range({*this, DataOffset},
 381                         SameNameIterator{*this, EndOffset});
 382     DataOffset = EndOffset;
 383     StrOffset = readStringOffsetAt(DataOffset);
 384   }
 385
 386   return EmptyRange;
 387 }
 388
 389 std::optional<uint32_t>
 390 AppleAcceleratorTable::idxOfHashInBucket(uint32_t HashToFind,
 391                                          uint32_t BucketIdx) const {
 392   std::optional<uint32_t> HashStartIdx = readIthBucket(BucketIdx);
 393   if (!HashStartIdx)
 394     return std::nullopt;
 395
 396   for (uint32_t HashIdx = *HashStartIdx; HashIdx < getNumHashes(); HashIdx++) {
 397     std::optional<uint32_t> MaybeHash = readIthHash(HashIdx);
 398     if (!MaybeHash || !wouldHashBeInBucket(*MaybeHash, BucketIdx))
 399       break;
 400     if (*MaybeHash == HashToFind)
 401       return HashIdx;
 402   }
 403   return std::nullopt;
 404 }
 405
 406 std::optional<StringRef> AppleAcceleratorTable::readStringFromStrSection(
 407     uint64_t StringSectionOffset) const {
 408   Error E = Error::success();
 409   StringRef Str = StringSection.getCStrRef(&StringSectionOffset, &E);
 410   if (E) {
 411     consumeError(std::move(E));
 412     return std::nullopt;
 413   }
 414   return Str;
 415 }
 416
 417 std::optional<uint32_t>
 418 AppleAcceleratorTable::readU32FromAccel(uint64_t &Offset,
 419                                         bool UseRelocation) const {
 420   Error E = Error::success();
 421   uint32_t Data = UseRelocation
 422                       ? AccelSection.getRelocatedValue(4, &Offset, nullptr, &E)
 423                       : AccelSection.getU32(&Offset, &E);
 424   if (E) {
 425     consumeError(std::move(E));
 426     return std::nullopt;
 427   }
 428   return Data;
 429 }
 430
 431 void DWARFDebugNames::Header::dump(ScopedPrinter &W) const {
 432   DictScope HeaderScope(W, "Header");
 433   W.printHex("Length", UnitLength);
 434   W.printString("Format", dwarf::FormatString(Format));
 435   W.printNumber("Version", Version);
 436   W.printNumber("CU count", CompUnitCount);
 437   W.printNumber("Local TU count", LocalTypeUnitCount);
 438   W.printNumber("Foreign TU count", ForeignTypeUnitCount);
 439   W.printNumber("Bucket count", BucketCount);
 440   W.printNumber("Name count", NameCount);
 441   W.printHex("Abbreviations table size", AbbrevTableSize);
 442   W.startLine() << "Augmentation: '" << AugmentationString << "'\n";
 443 }
 444
 445 Error DWARFDebugNames::Header::extract(const DWARFDataExtractor &AS,
 446                                              uint64_t *Offset) {
 447   auto HeaderError = [Offset = *Offset](Error E) {
 448     return createStringError(errc::illegal_byte_sequence,
 449                              "parsing .debug_names header at 0x%" PRIx64 ": %s",
 450                              Offset, toString(std::move(E)).c_str());
 451   };
 452
 453   DataExtractor::Cursor C(*Offset);
 454   std::tie(UnitLength, Format) = AS.getInitialLength(C);
 455
 456   Version = AS.getU16(C);
 457   AS.skip(C, 2); // padding
 458   CompUnitCount = AS.getU32(C);
 459   LocalTypeUnitCount = AS.getU32(C);
 460   ForeignTypeUnitCount = AS.getU32(C);
 461   BucketCount = AS.getU32(C);
 462   NameCount = AS.getU32(C);
 463   AbbrevTableSize = AS.getU32(C);
 464   AugmentationStringSize = alignTo(AS.getU32(C), 4);
 465
 466   if (!C)
 467     return HeaderError(C.takeError());
 468
 469   if (!AS.isValidOffsetForDataOfSize(C.tell(), AugmentationStringSize))
 470     return HeaderError(createStringError(errc::illegal_byte_sequence,
 471                                          "cannot read header augmentation"));
 472   AugmentationString.resize(AugmentationStringSize);
 473   AS.getU8(C, reinterpret_cast<uint8_t *>(AugmentationString.data()),
 474            AugmentationStringSize);
 475   *Offset = C.tell();
 476   return C.takeError();
 477 }
 478
 479 void DWARFDebugNames::Abbrev::dump(ScopedPrinter &W) const {
 480   DictScope AbbrevScope(W, ("Abbreviation 0x" + Twine::utohexstr(Code)).str());
 481   W.startLine() << formatv("Tag: {0}\n", Tag);
 482
 483   for (const auto &Attr : Attributes)
 484     W.startLine() << formatv("{0}: {1}\n", Attr.Index, Attr.Form);
 485 }
 486
 487 static constexpr DWARFDebugNames::AttributeEncoding sentinelAttrEnc() {
 488   return {dwarf::Index(0), dwarf::Form(0)};
 489 }
 490
 491 static bool isSentinel(const DWARFDebugNames::AttributeEncoding &AE) {
 492   return AE == sentinelAttrEnc();
 493 }
 494
 495 static DWARFDebugNames::Abbrev sentinelAbbrev() {
 496   return DWARFDebugNames::Abbrev(0, dwarf::Tag(0), 0, {});
 497 }
 498
 499 static bool isSentinel(const DWARFDebugNames::Abbrev &Abbr) {
 500   return Abbr.Code == 0;
 501 }
 502
 503 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getEmptyKey() {
 504   return sentinelAbbrev();
 505 }
 506
 507 DWARFDebugNames::Abbrev DWARFDebugNames::AbbrevMapInfo::getTombstoneKey() {
 508   return DWARFDebugNames::Abbrev(~0, dwarf::Tag(0), 0, {});
 509 }
 510
 511 Expected<DWARFDebugNames::AttributeEncoding>
 512 DWARFDebugNames::NameIndex::extractAttributeEncoding(uint64_t *Offset) {
 513   if (*Offset >= Offsets.EntriesBase) {
 514     return createStringError(errc::illegal_byte_sequence,
 515                              "Incorrectly terminated abbreviation table.");
 516   }
 517
 518   uint32_t Index = Section.AccelSection.getULEB128(Offset);
 519   uint32_t Form = Section.AccelSection.getULEB128(Offset);
 520   return AttributeEncoding(dwarf::Index(Index), dwarf::Form(Form));
 521 }
 522
 523 Expected<std::vector<DWARFDebugNames::AttributeEncoding>>
 524 DWARFDebugNames::NameIndex::extractAttributeEncodings(uint64_t *Offset) {
 525   std::vector<AttributeEncoding> Result;
 526   for (;;) {
 527     auto AttrEncOr = extractAttributeEncoding(Offset);
 528     if (!AttrEncOr)
 529       return AttrEncOr.takeError();
 530     if (isSentinel(*AttrEncOr))
 531       return std::move(Result);
 532
 533     Result.emplace_back(*AttrEncOr);
 534   }
 535 }
 536
 537 Expected<DWARFDebugNames::Abbrev>
 538 DWARFDebugNames::NameIndex::extractAbbrev(uint64_t *Offset) {
 539   if (*Offset >= Offsets.EntriesBase) {
 540     return createStringError(errc::illegal_byte_sequence,
 541                              "Incorrectly terminated abbreviation table.");
 542   }
 543   const uint64_t AbbrevOffset = *Offset;
 544   uint32_t Code = Section.AccelSection.getULEB128(Offset);
 545   if (Code == 0)
 546     return sentinelAbbrev();
 547
 548   uint32_t Tag = Section.AccelSection.getULEB128(Offset);
 549   auto AttrEncOr = extractAttributeEncodings(Offset);
 550   if (!AttrEncOr)
 551     return AttrEncOr.takeError();
 552   return Abbrev(Code, dwarf::Tag(Tag), AbbrevOffset, std::move(*AttrEncOr));
 553 }
 554
 555 DWARFDebugNames::DWARFDebugNamesOffsets
 556 dwarf::findDebugNamesOffsets(uint64_t EndOfHeaderOffset,
 557                              const DWARFDebugNames::Header &Hdr) {
 558   uint64_t DwarfSize = getDwarfOffsetByteSize(Hdr.Format);
 559   DWARFDebugNames::DWARFDebugNamesOffsets Ret;
 560   Ret.CUsBase = EndOfHeaderOffset;
 561   Ret.BucketsBase = Ret.CUsBase + Hdr.CompUnitCount * DwarfSize +
 562                     Hdr.LocalTypeUnitCount * DwarfSize +
 563                     Hdr.ForeignTypeUnitCount * 8;
 564   Ret.HashesBase = Ret.BucketsBase + Hdr.BucketCount * 4;
 565   Ret.StringOffsetsBase =
 566       Ret.HashesBase + (Hdr.BucketCount > 0 ? Hdr.NameCount * 4 : 0);
 567   Ret.EntryOffsetsBase = Ret.StringOffsetsBase + Hdr.NameCount * DwarfSize;
 568   Ret.EntriesBase =
 569       Ret.EntryOffsetsBase + Hdr.NameCount * DwarfSize + Hdr.AbbrevTableSize;
 570   return Ret;
 571 }
 572
 573 Error DWARFDebugNames::NameIndex::extract() {
 574   const DWARFDataExtractor &AS = Section.AccelSection;
 575   uint64_t EndOfHeaderOffset = Base;
 576   if (Error E = Hdr.extract(AS, &EndOfHeaderOffset))
 577     return E;
 578
 579   const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
 580   Offsets = dwarf::findDebugNamesOffsets(EndOfHeaderOffset, Hdr);
 581
 582   uint64_t Offset =
 583       Offsets.EntryOffsetsBase + (Hdr.NameCount * SectionOffsetSize);
 584
 585   if (!AS.isValidOffsetForDataOfSize(Offset, Hdr.AbbrevTableSize))
 586     return createStringError(errc::illegal_byte_sequence,
 587                              "Section too small: cannot read abbreviations.");
 588
 589   Offsets.EntriesBase = Offset + Hdr.AbbrevTableSize;
 590
 591   for (;;) {
 592     auto AbbrevOr = extractAbbrev(&Offset);
 593     if (!AbbrevOr)
 594       return AbbrevOr.takeError();
 595     if (isSentinel(*AbbrevOr))
 596       return Error::success();
 597
 598     if (!Abbrevs.insert(std::move(*AbbrevOr)).second)
 599       return createStringError(errc::invalid_argument,
 600                                "Duplicate abbreviation code.");
 601   }
 602 }
 603
 604 DWARFDebugNames::Entry::Entry(const NameIndex &NameIdx, const Abbrev &Abbr)
 605     : NameIdx(&NameIdx), Abbr(&Abbr) {
 606   // This merely creates form values. It is up to the caller
 607   // (NameIndex::getEntry) to populate them.
 608   Values.reserve(Abbr.Attributes.size());
 609   for (const auto &Attr : Abbr.Attributes)
 610     Values.emplace_back(Attr.Form);
 611 }
 612
 613 std::optional<DWARFFormValue>
 614 DWARFDebugNames::Entry::lookup(dwarf::Index Index) const {
 615   assert(Abbr->Attributes.size() == Values.size());
 616   for (auto Tuple : zip_first(Abbr->Attributes, Values)) {
 617     if (std::get<0>(Tuple).Index == Index)
 618       return std::get<1>(Tuple);
 619   }
 620   return std::nullopt;
 621 }
 622
 623 bool DWARFDebugNames::Entry::hasParentInformation() const {
 624   return lookup(dwarf::DW_IDX_parent).has_value();
 625 }
 626
 627 std::optional<uint64_t> DWARFDebugNames::Entry::getDIEUnitOffset() const {
 628   if (std::optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_die_offset))
 629     return Off->getAsReferenceUVal();
 630   return std::nullopt;
 631 }
 632
 633 std::optional<uint64_t> DWARFDebugNames::Entry::getRelatedCUIndex() const {
 634   // Return the DW_IDX_compile_unit attribute value if it is specified.
 635   if (std::optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_compile_unit))
 636     return Off->getAsUnsignedConstant();
 637   // In a per-CU index, the entries without a DW_IDX_compile_unit attribute
 638   // implicitly refer to the single CU.
 639   if (NameIdx->getCUCount() == 1)
 640     return 0;
 641   return std::nullopt;
 642 }
 643
 644 std::optional<uint64_t> DWARFDebugNames::Entry::getCUIndex() const {
 645   // Return the DW_IDX_compile_unit attribute value but only if we don't have a
 646   // DW_IDX_type_unit attribute. Use Entry::getRelatedCUIndex() to get the
 647   // associated CU index if this behaviour is not desired.
 648   if (lookup(dwarf::DW_IDX_type_unit).has_value())
 649     return std::nullopt;
 650   return getRelatedCUIndex();
 651 }
 652
 653 std::optional<uint64_t> DWARFDebugNames::Entry::getCUOffset() const {
 654   std::optional<uint64_t> Index = getCUIndex();
 655   if (!Index || *Index >= NameIdx->getCUCount())
 656     return std::nullopt;
 657   return NameIdx->getCUOffset(*Index);
 658 }
 659
 660 std::optional<uint64_t> DWARFDebugNames::Entry::getRelatedCUOffset() const {
 661   std::optional<uint64_t> Index = getRelatedCUIndex();
 662   if (!Index || *Index >= NameIdx->getCUCount())
 663     return std::nullopt;
 664   return NameIdx->getCUOffset(*Index);
 665 }
 666
 667 std::optional<uint64_t> DWARFDebugNames::Entry::getLocalTUOffset() const {
 668   std::optional<uint64_t> Index = getTUIndex();
 669   if (!Index || *Index >= NameIdx->getLocalTUCount())
 670     return std::nullopt;
 671   return NameIdx->getLocalTUOffset(*Index);
 672 }
 673
 674 std::optional<uint64_t>
 675 DWARFDebugNames::Entry::getForeignTUTypeSignature() const {
 676   std::optional<uint64_t> Index = getTUIndex();
 677   const uint32_t NumLocalTUs = NameIdx->getLocalTUCount();
 678   if (!Index || *Index < NumLocalTUs)
 679     return std::nullopt; // Invalid TU index or TU index is for a local TU
 680   // The foreign TU index is the TU index minus the number of local TUs.
 681   const uint64_t ForeignTUIndex = *Index - NumLocalTUs;
 682   if (ForeignTUIndex >= NameIdx->getForeignTUCount())
 683     return std::nullopt; // Invalid foreign TU index.
 684   return NameIdx->getForeignTUSignature(ForeignTUIndex);
 685 }
 686
 687 std::optional<uint64_t> DWARFDebugNames::Entry::getTUIndex() const {
 688   if (std::optional<DWARFFormValue> Off = lookup(dwarf::DW_IDX_type_unit))
 689     return Off->getAsUnsignedConstant();
 690   return std::nullopt;
 691 }
 692
 693 Expected<std::optional<DWARFDebugNames::Entry>>
 694 DWARFDebugNames::Entry::getParentDIEEntry() const {
 695   // The offset of the accelerator table entry for the parent.
 696   std::optional<DWARFFormValue> ParentEntryOff = lookup(dwarf::DW_IDX_parent);
 697   assert(ParentEntryOff.has_value() && "hasParentInformation() must be called");
 698
 699   if (ParentEntryOff->getForm() == dwarf::Form::DW_FORM_flag_present)
 700     return std::nullopt;
 701   return NameIdx->getEntryAtRelativeOffset(ParentEntryOff->getRawUValue());
 702 }
 703
 704 void DWARFDebugNames::Entry::dumpParentIdx(
 705     ScopedPrinter &W, const DWARFFormValue &FormValue) const {
 706   Expected<std::optional<Entry>> ParentEntry = getParentDIEEntry();
 707   if (!ParentEntry) {
 708     W.getOStream() << "<invalid offset data>";
 709     consumeError(ParentEntry.takeError());
 710     return;
 711   }
 712
 713   if (!ParentEntry->has_value()) {
 714     W.getOStream() << "<parent not indexed>";
 715     return;
 716   }
 717
 718   auto AbsoluteOffset = NameIdx->Offsets.EntriesBase + FormValue.getRawUValue();
 719   W.getOStream() << "Entry @ 0x" + Twine::utohexstr(AbsoluteOffset);
 720 }
 721
 722 void DWARFDebugNames::Entry::dump(ScopedPrinter &W) const {
 723   W.startLine() << formatv("Abbrev: {0:x}\n", Abbr->Code);
 724   W.startLine() << formatv("Tag: {0}\n", Abbr->Tag);
 725   assert(Abbr->Attributes.size() == Values.size());
 726   for (auto Tuple : zip_first(Abbr->Attributes, Values)) {
 727     auto Index = std::get<0>(Tuple).Index;
 728     W.startLine() << formatv("{0}: ", Index);
 729
 730     auto FormValue = std::get<1>(Tuple);
 731     if (Index == dwarf::Index::DW_IDX_parent)
 732       dumpParentIdx(W, FormValue);
 733     else
 734       FormValue.dump(W.getOStream());
 735     W.getOStream() << '\n';
 736   }
 737 }
 738
 739 char DWARFDebugNames::SentinelError::ID;
 740 std::error_code DWARFDebugNames::SentinelError::convertToErrorCode() const {
 741   return inconvertibleErrorCode();
 742 }
 743
 744 uint64_t DWARFDebugNames::NameIndex::getCUOffset(uint32_t CU) const {
 745   assert(CU < Hdr.CompUnitCount);
 746   const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
 747   uint64_t Offset = Offsets.CUsBase + SectionOffsetSize * CU;
 748   return Section.AccelSection.getRelocatedValue(SectionOffsetSize, &Offset);
 749 }
 750
 751 uint64_t DWARFDebugNames::NameIndex::getLocalTUOffset(uint32_t TU) const {
 752   assert(TU < Hdr.LocalTypeUnitCount);
 753   const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
 754   uint64_t Offset =
 755       Offsets.CUsBase + SectionOffsetSize * (Hdr.CompUnitCount + TU);
 756   return Section.AccelSection.getRelocatedValue(SectionOffsetSize, &Offset);
 757 }
 758
 759 uint64_t DWARFDebugNames::NameIndex::getForeignTUSignature(uint32_t TU) const {
 760   assert(TU < Hdr.ForeignTypeUnitCount);
 761   const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
 762   uint64_t Offset =
 763       Offsets.CUsBase +
 764       SectionOffsetSize * (Hdr.CompUnitCount + Hdr.LocalTypeUnitCount) + 8 * TU;
 765   return Section.AccelSection.getU64(&Offset);
 766 }
 767
 768 Expected<DWARFDebugNames::Entry>
 769 DWARFDebugNames::NameIndex::getEntry(uint64_t *Offset) const {
 770   const DWARFDataExtractor &AS = Section.AccelSection;
 771   if (!AS.isValidOffset(*Offset))
 772     return createStringError(errc::illegal_byte_sequence,
 773                              "Incorrectly terminated entry list.");
 774
 775   uint32_t AbbrevCode = AS.getULEB128(Offset);
 776   if (AbbrevCode == 0)
 777     return make_error<SentinelError>();
 778
 779   const auto AbbrevIt = Abbrevs.find_as(AbbrevCode);
 780   if (AbbrevIt == Abbrevs.end())
 781     return createStringError(errc::invalid_argument, "Invalid abbreviation.");
 782
 783   Entry E(*this, *AbbrevIt);
 784
 785   dwarf::FormParams FormParams = {Hdr.Version, 0, Hdr.Format};
 786   for (auto &Value : E.Values) {
 787     if (!Value.extractValue(AS, Offset, FormParams))
 788       return createStringError(errc::io_error,
 789                                "Error extracting index attribute values.");
 790   }
 791   return std::move(E);
 792 }
 793
 794 DWARFDebugNames::NameTableEntry
 795 DWARFDebugNames::NameIndex::getNameTableEntry(uint32_t Index) const {
 796   assert(0 < Index && Index <= Hdr.NameCount);
 797   const unsigned SectionOffsetSize = dwarf::getDwarfOffsetByteSize(Hdr.Format);
 798   uint64_t StringOffsetOffset =
 799       Offsets.StringOffsetsBase + SectionOffsetSize * (Index - 1);
 800   uint64_t EntryOffsetOffset =
 801       Offsets.EntryOffsetsBase + SectionOffsetSize * (Index - 1);
 802   const DWARFDataExtractor &AS = Section.AccelSection;
 803
 804   uint64_t StringOffset =
 805       AS.getRelocatedValue(SectionOffsetSize, &StringOffsetOffset);
 806   uint64_t EntryOffset = AS.getUnsigned(&EntryOffsetOffset, SectionOffsetSize);
 807   EntryOffset += Offsets.EntriesBase;
 808   return {Section.StringSection, Index, StringOffset, EntryOffset};
 809 }
 810
 811 uint32_t
 812 DWARFDebugNames::NameIndex::getBucketArrayEntry(uint32_t Bucket) const {
 813   assert(Bucket < Hdr.BucketCount);
 814   uint64_t BucketOffset = Offsets.BucketsBase + 4 * Bucket;
 815   return Section.AccelSection.getU32(&BucketOffset);
 816 }
 817
 818 uint32_t DWARFDebugNames::NameIndex::getHashArrayEntry(uint32_t Index) const {
 819   assert(0 < Index && Index <= Hdr.NameCount);
 820   uint64_t HashOffset = Offsets.HashesBase + 4 * (Index - 1);
 821   return Section.AccelSection.getU32(&HashOffset);
 822 }
 823
 824 // Returns true if we should continue scanning for entries, false if this is the
 825 // last (sentinel) entry). In case of a parsing error we also return false, as
 826 // it's not possible to recover this entry list (but the other lists may still
 827 // parse OK).
 828 bool DWARFDebugNames::NameIndex::dumpEntry(ScopedPrinter &W,
 829                                            uint64_t *Offset) const {
 830   uint64_t EntryId = *Offset;
 831   auto EntryOr = getEntry(Offset);
 832   if (!EntryOr) {
 833     handleAllErrors(EntryOr.takeError(), [](const SentinelError &) {},
 834                     [&W](const ErrorInfoBase &EI) { EI.log(W.startLine()); });
 835     return false;
 836   }
 837
 838   DictScope EntryScope(W, ("Entry @ 0x" + Twine::utohexstr(EntryId)).str());
 839   EntryOr->dump(W);
 840   return true;
 841 }
 842
 843 void DWARFDebugNames::NameIndex::dumpName(ScopedPrinter &W,
 844                                           const NameTableEntry &NTE,
 845                                           std::optional<uint32_t> Hash) const {
 846   DictScope NameScope(W, ("Name " + Twine(NTE.getIndex())).str());
 847   if (Hash)
 848     W.printHex("Hash", *Hash);
 849
 850   W.startLine() << format("String: 0x%08" PRIx64, NTE.getStringOffset());
 851   W.getOStream() << " \"" << NTE.getString() << "\"\n";
 852
 853   uint64_t EntryOffset = NTE.getEntryOffset();
 854   while (dumpEntry(W, &EntryOffset))
 855     /*empty*/;
 856 }
 857
 858 void DWARFDebugNames::NameIndex::dumpCUs(ScopedPrinter &W) const {
 859   ListScope CUScope(W, "Compilation Unit offsets");
 860   for (uint32_t CU = 0; CU < Hdr.CompUnitCount; ++CU)
 861     W.startLine() << format("CU[%u]: 0x%08" PRIx64 "\n", CU, getCUOffset(CU));
 862 }
 863
 864 void DWARFDebugNames::NameIndex::dumpLocalTUs(ScopedPrinter &W) const {
 865   if (Hdr.LocalTypeUnitCount == 0)
 866     return;
 867
 868   ListScope TUScope(W, "Local Type Unit offsets");
 869   for (uint32_t TU = 0; TU < Hdr.LocalTypeUnitCount; ++TU)
 870     W.startLine() << format("LocalTU[%u]: 0x%08" PRIx64 "\n", TU,
 871                             getLocalTUOffset(TU));
 872 }
 873
 874 void DWARFDebugNames::NameIndex::dumpForeignTUs(ScopedPrinter &W) const {
 875   if (Hdr.ForeignTypeUnitCount == 0)
 876     return;
 877
 878   ListScope TUScope(W, "Foreign Type Unit signatures");
 879   for (uint32_t TU = 0; TU < Hdr.ForeignTypeUnitCount; ++TU) {
 880     W.startLine() << format("ForeignTU[%u]: 0x%016" PRIx64 "\n", TU,
 881                             getForeignTUSignature(TU));
 882   }
 883 }
 884
 885 void DWARFDebugNames::NameIndex::dumpAbbreviations(ScopedPrinter &W) const {
 886   ListScope AbbrevsScope(W, "Abbreviations");
 887   std::vector<const Abbrev *> AbbrevsVect;
 888   for (const DWARFDebugNames::Abbrev &Abbr : Abbrevs)
 889     AbbrevsVect.push_back(&Abbr);
 890   llvm::sort(AbbrevsVect, [](const Abbrev *LHS, const Abbrev *RHS) {
 891     return LHS->AbbrevOffset < RHS->AbbrevOffset;
 892   });
 893   for (const DWARFDebugNames::Abbrev *Abbr : AbbrevsVect)
 894     Abbr->dump(W);
 895 }
 896
 897 void DWARFDebugNames::NameIndex::dumpBucket(ScopedPrinter &W,
 898                                             uint32_t Bucket) const {
 899   ListScope BucketScope(W, ("Bucket " + Twine(Bucket)).str());
 900   uint32_t Index = getBucketArrayEntry(Bucket);
 901   if (Index == 0) {
 902     W.printString("EMPTY");
 903     return;
 904   }
 905   if (Index > Hdr.NameCount) {
 906     W.printString("Name index is invalid");
 907     return;
 908   }
 909
 910   for (; Index <= Hdr.NameCount; ++Index) {
 911     uint32_t Hash = getHashArrayEntry(Index);
 912     if (Hash % Hdr.BucketCount != Bucket)
 913       break;
 914
 915     dumpName(W, getNameTableEntry(Index), Hash);
 916   }
 917 }
 918
 919 LLVM_DUMP_METHOD void DWARFDebugNames::NameIndex::dump(ScopedPrinter &W) const {
 920   DictScope UnitScope(W, ("Name Index @ 0x" + Twine::utohexstr(Base)).str());
 921   Hdr.dump(W);
 922   dumpCUs(W);
 923   dumpLocalTUs(W);
 924   dumpForeignTUs(W);
 925   dumpAbbreviations(W);
 926
 927   if (Hdr.BucketCount > 0) {
 928     for (uint32_t Bucket = 0; Bucket < Hdr.BucketCount; ++Bucket)
 929       dumpBucket(W, Bucket);
 930     return;
 931   }
 932
 933   W.startLine() << "Hash table not present\n";
 934   for (const NameTableEntry &NTE : *this)
 935     dumpName(W, NTE, std::nullopt);
 936 }
 937
 938 Error DWARFDebugNames::extract() {
 939   uint64_t Offset = 0;
 940   while (AccelSection.isValidOffset(Offset)) {
 941     NameIndex Next(*this, Offset);
 942     if (Error E = Next.extract())
 943       return E;
 944     Offset = Next.getNextUnitOffset();
 945     NameIndices.push_back(std::move(Next));
 946   }
 947   return Error::success();
 948 }
 949
 950 iterator_range<DWARFDebugNames::ValueIterator>
 951 DWARFDebugNames::NameIndex::equal_range(StringRef Key) const {
 952   return make_range(ValueIterator(*this, Key), ValueIterator());
 953 }
 954
 955 LLVM_DUMP_METHOD void DWARFDebugNames::dump(raw_ostream &OS) const {
 956   ScopedPrinter W(OS);
 957   for (const NameIndex &NI : NameIndices)
 958     NI.dump(W);
 959 }
 960
 961 std::optional<uint64_t>
 962 DWARFDebugNames::ValueIterator::findEntryOffsetInCurrentIndex() {
 963   const Header &Hdr = CurrentIndex->Hdr;
 964   if (Hdr.BucketCount == 0) {
 965     // No Hash Table, We need to search through all names in the Name Index.
 966     for (const NameTableEntry &NTE : *CurrentIndex) {
 967       if (NTE.sameNameAs(Key))
 968         return NTE.getEntryOffset();
 969     }
 970     return std::nullopt;
 971   }
 972
 973   // The Name Index has a Hash Table, so use that to speed up the search.
 974   // Compute the Key Hash, if it has not been done already.
 975   if (!Hash)
 976     Hash = caseFoldingDjbHash(Key);
 977   uint32_t Bucket = *Hash % Hdr.BucketCount;
 978   uint32_t Index = CurrentIndex->getBucketArrayEntry(Bucket);
 979   if (Index == 0)
 980     return std::nullopt; // Empty bucket
 981
 982   for (; Index <= Hdr.NameCount; ++Index) {
 983     uint32_t HashAtIndex = CurrentIndex->getHashArrayEntry(Index);
 984     if (HashAtIndex % Hdr.BucketCount != Bucket)
 985       return std::nullopt; // End of bucket
 986     // Only compare names if the hashes match.
 987     if (HashAtIndex != Hash)
 988       continue;
 989
 990     NameTableEntry NTE = CurrentIndex->getNameTableEntry(Index);
 991     if (NTE.sameNameAs(Key))
 992       return NTE.getEntryOffset();
 993   }
 994   return std::nullopt;
 995 }
 996
 997 bool DWARFDebugNames::ValueIterator::getEntryAtCurrentOffset() {
 998   auto EntryOr = CurrentIndex->getEntry(&DataOffset);
 999   if (!EntryOr) {
1000     consumeError(EntryOr.takeError());
1001     return false;
1002   }
1003   CurrentEntry = std::move(*EntryOr);
1004   return true;
1005 }
1006
1007 bool DWARFDebugNames::ValueIterator::findInCurrentIndex() {
1008   std::optional<uint64_t> Offset = findEntryOffsetInCurrentIndex();
1009   if (!Offset)
1010     return false;
1011   DataOffset = *Offset;
1012   return getEntryAtCurrentOffset();
1013 }
1014
1015 void DWARFDebugNames::ValueIterator::searchFromStartOfCurrentIndex() {
1016   for (const NameIndex *End = CurrentIndex->Section.NameIndices.end();
1017        CurrentIndex != End; ++CurrentIndex) {
1018     if (findInCurrentIndex())
1019       return;
1020   }
1021   setEnd();
1022 }
1023
1024 void DWARFDebugNames::ValueIterator::next() {
1025   assert(CurrentIndex && "Incrementing an end() iterator?");
1026
1027   // First try the next entry in the current Index.
1028   if (getEntryAtCurrentOffset())
1029     return;
1030
1031   // If we're a local iterator or we have reached the last Index, we're done.
1032   if (IsLocal || CurrentIndex == &CurrentIndex->Section.NameIndices.back()) {
1033     setEnd();
1034     return;
1035   }
1036
1037   // Otherwise, try the next index.
1038   ++CurrentIndex;
1039   searchFromStartOfCurrentIndex();
1040 }
1041
1042 DWARFDebugNames::ValueIterator::ValueIterator(const DWARFDebugNames &AccelTable,
1043                                               StringRef Key)
1044     : CurrentIndex(AccelTable.NameIndices.begin()), IsLocal(false),
1045       Key(std::string(Key)) {
1046   searchFromStartOfCurrentIndex();
1047 }
1048
1049 DWARFDebugNames::ValueIterator::ValueIterator(
1050     const DWARFDebugNames::NameIndex &NI, StringRef Key)
1051     : CurrentIndex(&NI), IsLocal(true), Key(std::string(Key)) {
1052   if (!findInCurrentIndex())
1053     setEnd();
1054 }
1055
1056 iterator_range<DWARFDebugNames::ValueIterator>
1057 DWARFDebugNames::equal_range(StringRef Key) const {
1058   if (NameIndices.empty())
1059     return make_range(ValueIterator(), ValueIterator());
1060   return make_range(ValueIterator(*this, Key), ValueIterator());
1061 }
1062
1063 const DWARFDebugNames::NameIndex *
1064 DWARFDebugNames::getCUOrTUNameIndex(uint64_t UnitOffset) {
1065   if (UnitOffsetToNameIndex.size() == 0 && NameIndices.size() > 0) {
1066     for (const auto &NI : *this) {
1067       for (uint32_t CU = 0; CU < NI.getCUCount(); ++CU)
1068         UnitOffsetToNameIndex.try_emplace(NI.getCUOffset(CU), &NI);
1069       for (uint32_t TU = 0; TU < NI.getLocalTUCount(); ++TU)
1070         UnitOffsetToNameIndex.try_emplace(NI.getLocalTUOffset(TU), &NI);
1071     }
1072   }
1073   return UnitOffsetToNameIndex.lookup(UnitOffset);
1074 }
1075
1076 static bool isObjCSelector(StringRef Name) {
1077   return Name.size() > 2 && (Name[0] == '-' || Name[0] == '+') &&
1078          (Name[1] == '[');
1079 }
1080
1081 std::optional<ObjCSelectorNames> llvm::getObjCNamesIfSelector(StringRef Name) {
1082   if (!isObjCSelector(Name))
1083     return std::nullopt;
1084   // "-[Atom setMass:]"
1085   StringRef ClassNameStart(Name.drop_front(2));
1086   size_t FirstSpace = ClassNameStart.find(' ');
1087   if (FirstSpace == StringRef::npos)
1088     return std::nullopt;
1089
1090   StringRef SelectorStart = ClassNameStart.drop_front(FirstSpace + 1);
1091   if (!SelectorStart.size())
1092     return std::nullopt;
1093
1094   ObjCSelectorNames Ans;
1095   Ans.ClassName = ClassNameStart.take_front(FirstSpace);
1096   Ans.Selector = SelectorStart.drop_back(); // drop ']';
1097
1098   // "-[Class(Category) selector :withArg ...]"
1099   if (Ans.ClassName.back() == ')') {
1100     size_t OpenParens = Ans.ClassName.find('(');
1101     if (OpenParens != StringRef::npos) {
1102       Ans.ClassNameNoCategory = Ans.ClassName.take_front(OpenParens);
1103
1104       Ans.MethodNameNoCategory = Name.take_front(OpenParens + 2);
1105       // FIXME: The missing space here may be a bug, but dsymutil-classic also
1106       // does it this way.
1107       append_range(*Ans.MethodNameNoCategory, SelectorStart);
1108     }
1109   }
1110   return Ans;
1111 }
1112
1113 std::optional<StringRef> llvm::StripTemplateParameters(StringRef Name) {
1114   // We are looking for template parameters to strip from Name. e.g.
1115   //
1116   //  operator<<B>
1117   //
1118   // We look for > at the end but if it does not contain any < then we
1119   // have something like operator>>. We check for the operator<=> case.
1120   if (!Name.ends_with(">") || Name.count("<") == 0 || Name.ends_with("<=>"))
1121     return {};
1122
1123   // How many < until we have the start of the template parameters.
1124   size_t NumLeftAnglesToSkip = 1;
1125
1126   // If we have operator<=> then we need to skip its < as well.
1127   NumLeftAnglesToSkip += Name.count("<=>");
1128
1129   size_t RightAngleCount = Name.count('>');
1130   size_t LeftAngleCount = Name.count('<');
1131
1132   // If we have more < than > we have operator< or operator<<
1133   // we to account for their < as well.
1134   if (LeftAngleCount > RightAngleCount)
1135     NumLeftAnglesToSkip += LeftAngleCount - RightAngleCount;
1136
1137   size_t StartOfTemplate = 0;
1138   while (NumLeftAnglesToSkip--)
1139     StartOfTemplate = Name.find('<', StartOfTemplate) + 1;
1140
1141   return Name.substr(0, StartOfTemplate - 1);
1142 }