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