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