1//===- DWARFAcceleratorTable.h ----------------------------------*- C++ -*-===//
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#ifndef LLVM_DEBUGINFO_DWARF_DWARFACCELERATORTABLE_H
10#define LLVM_DEBUGINFO_DWARF_DWARFACCELERATORTABLE_H
11
12#include "llvm/ADT/DenseSet.h"
13#include "llvm/ADT/SmallString.h"
14#include "llvm/ADT/SmallVector.h"
15#include "llvm/BinaryFormat/Dwarf.h"
16#include "llvm/DebugInfo/DWARF/DWARFDataExtractor.h"
17#include "llvm/DebugInfo/DWARF/DWARFFormValue.h"
18#include <cstdint>
19#include <utility>
20
21namespace llvm {
22
23class raw_ostream;
24class ScopedPrinter;
25
26/// The accelerator tables are designed to allow efficient random access
27/// (using a symbol name as a key) into debug info by providing an index of the
28/// debug info DIEs. This class implements the common functionality of Apple and
29/// DWARF 5 accelerator tables.
30/// TODO: Generalize the rest of the AppleAcceleratorTable interface and move it
31/// to this class.
32class DWARFAcceleratorTable {
33protected:
34 DWARFDataExtractor AccelSection;
35 DataExtractor StringSection;
36
37public:
38 /// An abstract class representing a single entry in the accelerator tables.
39 class Entry {
40 protected:
41 SmallVector<DWARFFormValue, 3> Values;
42
43 Entry() = default;
44
45 // Make these protected so only (final) subclasses can be copied around.
46 Entry(const Entry &) = default;
47 Entry(Entry &&) = default;
48 Entry &operator=(const Entry &) = default;
49 Entry &operator=(Entry &&) = default;
50 ~Entry() = default;
51
52
53 public:
54 /// Returns the Offset of the Compilation Unit associated with this
55 /// Accelerator Entry or std::nullopt if the Compilation Unit offset is not
56 /// recorded in this Accelerator Entry.
57 virtual std::optional<uint64_t> getCUOffset() const = 0;
58
59 /// Returns the Offset of the Type Unit associated with this
60 /// Accelerator Entry or std::nullopt if the Type Unit offset is not
61 /// recorded in this Accelerator Entry.
62 virtual std::optional<uint64_t> getLocalTUOffset() const {
63 // Default return for accelerator tables that don't support type units.
64 return std::nullopt;
65 }
66
67 /// Returns the type signature of the Type Unit associated with this
68 /// Accelerator Entry or std::nullopt if the Type Unit offset is not
69 /// recorded in this Accelerator Entry.
70 virtual std::optional<uint64_t> getForeignTUTypeSignature() const {
71 // Default return for accelerator tables that don't support type units.
72 return std::nullopt;
73 }
74
75 /// Returns the Tag of the Debug Info Entry associated with this
76 /// Accelerator Entry or std::nullopt if the Tag is not recorded in this
77 /// Accelerator Entry.
78 virtual std::optional<dwarf::Tag> getTag() const = 0;
79
80 /// Returns the raw values of fields in the Accelerator Entry. In general,
81 /// these can only be interpreted with the help of the metadata in the
82 /// owning Accelerator Table.
83 ArrayRef<DWARFFormValue> getValues() const { return Values; }
84 };
85
86 DWARFAcceleratorTable(const DWARFDataExtractor &AccelSection,
87 DataExtractor StringSection)
88 : AccelSection(AccelSection), StringSection(StringSection) {}
89 virtual ~DWARFAcceleratorTable();
90
91 virtual Error extract() = 0;
92 virtual void dump(raw_ostream &OS) const = 0;
93
94 DWARFAcceleratorTable(const DWARFAcceleratorTable &) = delete;
95 void operator=(const DWARFAcceleratorTable &) = delete;
96};
97
98/// This implements the Apple accelerator table format, a precursor of the
99/// DWARF 5 accelerator table format.
100class AppleAcceleratorTable : public DWARFAcceleratorTable {
101 struct Header {
102 uint32_t Magic;
103 uint16_t Version;
104 uint16_t HashFunction;
105 uint32_t BucketCount;
106 uint32_t HashCount;
107 uint32_t HeaderDataLength;
108
109 void dump(ScopedPrinter &W) const;
110 };
111
112 struct HeaderData {
113 using AtomType = uint16_t;
114 using Form = dwarf::Form;
115
116 uint64_t DIEOffsetBase;
117 SmallVector<std::pair<AtomType, Form>, 3> Atoms;
118
119 std::optional<uint64_t>
120 extractOffset(std::optional<DWARFFormValue> Value) const;
121 };
122
123 Header Hdr;
124 HeaderData HdrData;
125 dwarf::FormParams FormParams;
126 uint32_t HashDataEntryLength;
127 bool IsValid = false;
128
129 /// Returns true if we should continue scanning for entries or false if we've
130 /// reached the last (sentinel) entry of encountered a parsing error.
131 bool dumpName(ScopedPrinter &W, SmallVectorImpl<DWARFFormValue> &AtomForms,
132 uint64_t *DataOffset) const;
133
134 /// Reads an uint32_t from the accelerator table at Offset, which is
135 /// incremented by the number of bytes read.
136 std::optional<uint32_t> readU32FromAccel(uint64_t &Offset,
137 bool UseRelocation = false) const;
138
139 /// Reads a StringRef from the string table at Offset.
140 std::optional<StringRef>
141 readStringFromStrSection(uint64_t StringSectionOffset) const;
142
143 /// Return the offset into the section where the Buckets begin.
144 uint64_t getBucketBase() const { return sizeof(Hdr) + Hdr.HeaderDataLength; }
145
146 /// Return the offset into the section where the I-th bucket is.
147 uint64_t getIthBucketBase(uint32_t I) const {
148 return getBucketBase() + I * 4;
149 }
150
151 /// Return the offset into the section where the hash list begins.
152 uint64_t getHashBase() const { return getBucketBase() + getNumBuckets() * 4; }
153
154 /// Return the offset into the section where the I-th hash is.
155 uint64_t getIthHashBase(uint32_t I) const { return getHashBase() + I * 4; }
156
157 /// Return the offset into the section where the offset list begins.
158 uint64_t getOffsetBase() const { return getHashBase() + getNumHashes() * 4; }
159
160 /// Return the offset into the section where the table entries begin.
161 uint64_t getEntriesBase() const {
162 return getOffsetBase() + getNumHashes() * 4;
163 }
164
165 /// Return the offset into the section where the I-th offset is.
166 uint64_t getIthOffsetBase(uint32_t I) const {
167 return getOffsetBase() + I * 4;
168 }
169
170 /// Returns the index of the bucket where a hypothetical Hash would be.
171 uint32_t hashToBucketIdx(uint32_t Hash) const {
172 return Hash % getNumBuckets();
173 }
174
175 /// Returns true iff a hypothetical Hash would be assigned to the BucketIdx-th
176 /// bucket.
177 bool wouldHashBeInBucket(uint32_t Hash, uint32_t BucketIdx) const {
178 return hashToBucketIdx(Hash) == BucketIdx;
179 }
180
181 /// Reads the contents of the I-th bucket, that is, the index in the hash list
182 /// where the hashes corresponding to this bucket begin.
183 std::optional<uint32_t> readIthBucket(uint32_t I) const {
184 uint64_t Offset = getIthBucketBase(I);
185 return readU32FromAccel(Offset);
186 }
187
188 /// Reads the I-th hash in the hash list.
189 std::optional<uint32_t> readIthHash(uint32_t I) const {
190 uint64_t Offset = getIthHashBase(I);
191 return readU32FromAccel(Offset);
192 }
193
194 /// Reads the I-th offset in the offset list.
195 std::optional<uint32_t> readIthOffset(uint32_t I) const {
196 uint64_t Offset = getIthOffsetBase(I);
197 return readU32FromAccel(Offset);
198 }
199
200 /// Reads a string offset from the accelerator table at Offset, which is
201 /// incremented by the number of bytes read.
202 std::optional<uint32_t> readStringOffsetAt(uint64_t &Offset) const {
203 return readU32FromAccel(Offset, /*UseRelocation*/ UseRelocation: true);
204 }
205
206 /// Scans through all Hashes in the BucketIdx-th bucket, attempting to find
207 /// HashToFind. If it is found, its index in the list of hashes is returned.
208 std::optional<uint32_t> idxOfHashInBucket(uint32_t HashToFind,
209 uint32_t BucketIdx) const;
210
211public:
212 /// Apple-specific implementation of an Accelerator Entry.
213 class Entry final : public DWARFAcceleratorTable::Entry {
214 const AppleAcceleratorTable &Table;
215
216 Entry(const AppleAcceleratorTable &Table);
217 void extract(uint64_t *Offset);
218
219 public:
220 std::optional<uint64_t> getCUOffset() const override;
221
222 /// Returns the Section Offset of the Debug Info Entry associated with this
223 /// Accelerator Entry or std::nullopt if the DIE offset is not recorded in
224 /// this Accelerator Entry. The returned offset is relative to the start of
225 /// the Section containing the DIE.
226 std::optional<uint64_t> getDIESectionOffset() const;
227
228 std::optional<dwarf::Tag> getTag() const override;
229
230 /// Returns the value of the Atom in this Accelerator Entry, if the Entry
231 /// contains such Atom.
232 std::optional<DWARFFormValue> lookup(HeaderData::AtomType Atom) const;
233
234 friend class AppleAcceleratorTable;
235 friend class ValueIterator;
236 };
237
238 /// An iterator for Entries all having the same string as key.
239 class SameNameIterator
240 : public iterator_facade_base<SameNameIterator, std::forward_iterator_tag,
241 Entry> {
242 Entry Current;
243 uint64_t Offset = 0;
244
245 public:
246 /// Construct a new iterator for the entries at \p DataOffset.
247 SameNameIterator(const AppleAcceleratorTable &AccelTable,
248 uint64_t DataOffset);
249
250 const Entry &operator*() {
251 uint64_t OffsetCopy = Offset;
252 Current.extract(Offset: &OffsetCopy);
253 return Current;
254 }
255 SameNameIterator &operator++() {
256 Offset += Current.Table.getHashDataEntryLength();
257 return *this;
258 }
259 friend bool operator==(const SameNameIterator &A,
260 const SameNameIterator &B) {
261 return A.Offset == B.Offset;
262 }
263 };
264
265 struct EntryWithName {
266 EntryWithName(const AppleAcceleratorTable &Table)
267 : BaseEntry(Table), StrOffset(0) {}
268
269 std::optional<StringRef> readName() const {
270 return BaseEntry.Table.readStringFromStrSection(StringSectionOffset: StrOffset);
271 }
272
273 Entry BaseEntry;
274 uint32_t StrOffset;
275 };
276
277 /// An iterator for all entries in the table.
278 class Iterator
279 : public iterator_facade_base<Iterator, std::forward_iterator_tag,
280 EntryWithName> {
281 constexpr static auto EndMarker = std::numeric_limits<uint64_t>::max();
282
283 EntryWithName Current;
284 uint64_t Offset = EndMarker;
285 uint32_t NumEntriesToCome = 0;
286
287 void setToEnd() { Offset = EndMarker; }
288 bool isEnd() const { return Offset == EndMarker; }
289 const AppleAcceleratorTable &getTable() const {
290 return Current.BaseEntry.Table;
291 }
292
293 /// Reads the next Entry in the table, populating `Current`.
294 /// If not possible (e.g. end of the section), becomes the end iterator.
295 void prepareNextEntryOrEnd();
296
297 /// Reads the next string pointer and the entry count for that string,
298 /// populating `NumEntriesToCome`.
299 /// If not possible (e.g. end of the section), becomes the end iterator.
300 /// Assumes `Offset` points to a string reference.
301 void prepareNextStringOrEnd();
302
303 public:
304 Iterator(const AppleAcceleratorTable &Table, bool SetEnd = false);
305
306 Iterator &operator++() {
307 prepareNextEntryOrEnd();
308 return *this;
309 }
310 bool operator==(const Iterator &It) const { return Offset == It.Offset; }
311 const EntryWithName &operator*() const {
312 assert(!isEnd() && "dereferencing end iterator");
313 return Current;
314 }
315 };
316
317 AppleAcceleratorTable(const DWARFDataExtractor &AccelSection,
318 DataExtractor StringSection)
319 : DWARFAcceleratorTable(AccelSection, StringSection) {}
320
321 Error extract() override;
322 uint32_t getNumBuckets() const;
323 uint32_t getNumHashes() const;
324 uint32_t getSizeHdr() const;
325 uint32_t getHeaderDataLength() const;
326
327 /// Returns the size of one HashData entry.
328 uint32_t getHashDataEntryLength() const { return HashDataEntryLength; }
329
330 /// Return the Atom description, which can be used to interpret the raw values
331 /// of the Accelerator Entries in this table.
332 ArrayRef<std::pair<HeaderData::AtomType, HeaderData::Form>> getAtomsDesc();
333
334 /// Returns true iff `AtomTy` is one of the atoms available in Entries of this
335 /// table.
336 bool containsAtomType(HeaderData::AtomType AtomTy) const {
337 return is_contained(Range: make_first_range(c: HdrData.Atoms), Element: AtomTy);
338 }
339
340 bool validateForms();
341
342 /// Return information related to the DWARF DIE we're looking for when
343 /// performing a lookup by name.
344 ///
345 /// \param HashDataOffset an offset into the hash data table
346 /// \returns <DieOffset, DieTag>
347 /// DieOffset is the offset into the .debug_info section for the DIE
348 /// related to the input hash data offset.
349 /// DieTag is the tag of the DIE
350 std::pair<uint64_t, dwarf::Tag> readAtoms(uint64_t *HashDataOffset);
351 void dump(raw_ostream &OS) const override;
352
353 /// Look up all entries in the accelerator table matching \c Key.
354 iterator_range<SameNameIterator> equal_range(StringRef Key) const;
355
356 /// Lookup all entries in the accelerator table.
357 auto entries() const {
358 return make_range(x: Iterator(*this), y: Iterator(*this, /*SetEnd*/ true));
359 }
360};
361
362/// .debug_names section consists of one or more units. Each unit starts with a
363/// header, which is followed by a list of compilation units, local and foreign
364/// type units.
365///
366/// These may be followed by an (optional) hash lookup table, which consists of
367/// an array of buckets and hashes similar to the apple tables above. The only
368/// difference is that the hashes array is 1-based, and consequently an empty
369/// bucket is denoted by 0 and not UINT32_MAX.
370///
371/// Next is the name table, which consists of an array of names and array of
372/// entry offsets. This is different from the apple tables, which store names
373/// next to the actual entries.
374///
375/// The structure of the entries is described by an abbreviations table, which
376/// comes after the name table. Unlike the apple tables, which have a uniform
377/// entry structure described in the header, each .debug_names entry may have
378/// different index attributes (DW_IDX_???) attached to it.
379///
380/// The last segment consists of a list of entries, which is a 0-terminated list
381/// referenced by the name table and interpreted with the help of the
382/// abbreviation table.
383class DWARFDebugNames : public DWARFAcceleratorTable {
384public:
385 class NameIndex;
386 class NameIterator;
387 class ValueIterator;
388
389 /// DWARF v5 Name Index header.
390 struct Header {
391 uint64_t UnitLength;
392 dwarf::DwarfFormat Format;
393 uint16_t Version;
394 uint32_t CompUnitCount;
395 uint32_t LocalTypeUnitCount;
396 uint32_t ForeignTypeUnitCount;
397 uint32_t BucketCount;
398 uint32_t NameCount;
399 uint32_t AbbrevTableSize;
400 uint32_t AugmentationStringSize;
401 SmallString<8> AugmentationString;
402
403 Error extract(const DWARFDataExtractor &AS, uint64_t *Offset);
404 void dump(ScopedPrinter &W) const;
405 };
406
407 /// Index attribute and its encoding.
408 struct AttributeEncoding {
409 dwarf::Index Index;
410 dwarf::Form Form;
411
412 constexpr AttributeEncoding(dwarf::Index Index, dwarf::Form Form)
413 : Index(Index), Form(Form) {}
414
415 friend bool operator==(const AttributeEncoding &LHS,
416 const AttributeEncoding &RHS) {
417 return LHS.Index == RHS.Index && LHS.Form == RHS.Form;
418 }
419 };
420
421 /// Abbreviation describing the encoding of Name Index entries.
422 struct Abbrev {
423 uint64_t AbbrevOffset; /// < Abbreviation offset in the .debug_names section
424 uint32_t Code; ///< Abbreviation code
425 dwarf::Tag Tag; ///< Dwarf Tag of the described entity.
426 std::vector<AttributeEncoding> Attributes; ///< List of index attributes.
427
428 Abbrev(uint32_t Code, dwarf::Tag Tag, uint64_t AbbrevOffset,
429 std::vector<AttributeEncoding> Attributes)
430 : AbbrevOffset(AbbrevOffset), Code(Code), Tag(Tag),
431 Attributes(std::move(Attributes)) {}
432
433 void dump(ScopedPrinter &W) const;
434 };
435
436 /// DWARF v5-specific implementation of an Accelerator Entry.
437 class Entry final : public DWARFAcceleratorTable::Entry {
438 const NameIndex *NameIdx;
439 const Abbrev *Abbr;
440
441 Entry(const NameIndex &NameIdx, const Abbrev &Abbr);
442
443 public:
444 const NameIndex *getNameIndex() const { return NameIdx; }
445 std::optional<uint64_t> getCUOffset() const override;
446 std::optional<uint64_t> getLocalTUOffset() const override;
447 std::optional<uint64_t> getForeignTUTypeSignature() const override;
448 std::optional<dwarf::Tag> getTag() const override { return tag(); }
449
450 // Special function that will return the related CU offset needed type
451 // units. This gets used to find the .dwo file that originated the entries
452 // for a given type unit.
453 std::optional<uint64_t> getRelatedCUOffset() const;
454
455 /// Returns the Index into the Compilation Unit list of the owning Name
456 /// Index or std::nullopt if this Accelerator Entry does not have an
457 /// associated Compilation Unit. It is up to the user to verify that the
458 /// returned Index is valid in the owning NameIndex (or use getCUOffset(),
459 /// which will handle that check itself). Note that entries in NameIndexes
460 /// which index just a single Compilation Unit are implicitly associated
461 /// with that unit, so this function will return 0 even without an explicit
462 /// DW_IDX_compile_unit attribute, unless there is a DW_IDX_type_unit
463 /// attribute.
464 std::optional<uint64_t> getCUIndex() const;
465
466 /// Similar functionality to getCUIndex() but without the DW_IDX_type_unit
467 /// restriction. This allows us to get the associated a compilation unit
468 /// index for an entry that is a type unit.
469 std::optional<uint64_t> getRelatedCUIndex() const;
470
471 /// Returns the Index into the Local Type Unit list of the owning Name
472 /// Index or std::nullopt if this Accelerator Entry does not have an
473 /// associated Type Unit. It is up to the user to verify that the
474 /// returned Index is valid in the owning NameIndex (or use
475 /// getLocalTUOffset(), which will handle that check itself).
476 std::optional<uint64_t> getLocalTUIndex() const;
477
478 /// .debug_names-specific getter, which always succeeds (DWARF v5 index
479 /// entries always have a tag).
480 dwarf::Tag tag() const { return Abbr->Tag; }
481
482 /// Returns the Offset of the DIE within the containing CU or TU.
483 std::optional<uint64_t> getDIEUnitOffset() const;
484
485 /// Returns true if this Entry has information about its parent DIE (i.e. if
486 /// it has an IDX_parent attribute)
487 bool hasParentInformation() const;
488
489 /// Returns the Entry corresponding to the parent of the DIE represented by
490 /// `this` Entry. If the parent is not in the table, nullopt is returned.
491 /// Precondition: hasParentInformation() == true.
492 /// An error is returned for ill-formed tables.
493 Expected<std::optional<DWARFDebugNames::Entry>> getParentDIEEntry() const;
494
495 /// Return the Abbreviation that can be used to interpret the raw values of
496 /// this Accelerator Entry.
497 const Abbrev &getAbbrev() const { return *Abbr; }
498
499 /// Returns the value of the Index Attribute in this Accelerator Entry, if
500 /// the Entry contains such Attribute.
501 std::optional<DWARFFormValue> lookup(dwarf::Index Index) const;
502
503 void dump(ScopedPrinter &W) const;
504 void dumpParentIdx(ScopedPrinter &W, const DWARFFormValue &FormValue) const;
505
506 friend class NameIndex;
507 friend class ValueIterator;
508 };
509
510 /// Error returned by NameIndex::getEntry to report it has reached the end of
511 /// the entry list.
512 class SentinelError : public ErrorInfo<SentinelError> {
513 public:
514 static char ID;
515
516 void log(raw_ostream &OS) const override { OS << "Sentinel"; }
517 std::error_code convertToErrorCode() const override;
518 };
519
520private:
521 /// DenseMapInfo for struct Abbrev.
522 struct AbbrevMapInfo {
523 static Abbrev getEmptyKey();
524 static Abbrev getTombstoneKey();
525 static unsigned getHashValue(uint32_t Code) {
526 return DenseMapInfo<uint32_t>::getHashValue(Val: Code);
527 }
528 static unsigned getHashValue(const Abbrev &Abbr) {
529 return getHashValue(Code: Abbr.Code);
530 }
531 static bool isEqual(uint32_t LHS, const Abbrev &RHS) {
532 return LHS == RHS.Code;
533 }
534 static bool isEqual(const Abbrev &LHS, const Abbrev &RHS) {
535 return LHS.Code == RHS.Code;
536 }
537 };
538
539public:
540 /// A single entry in the Name Table (DWARF v5 sect. 6.1.1.4.6) of the Name
541 /// Index.
542 class NameTableEntry {
543 DataExtractor StrData;
544
545 uint32_t Index;
546 uint64_t StringOffset;
547 uint64_t EntryOffset;
548
549 public:
550 NameTableEntry(const DataExtractor &StrData, uint32_t Index,
551 uint64_t StringOffset, uint64_t EntryOffset)
552 : StrData(StrData), Index(Index), StringOffset(StringOffset),
553 EntryOffset(EntryOffset) {}
554
555 /// Return the index of this name in the parent Name Index.
556 uint32_t getIndex() const { return Index; }
557
558 /// Returns the offset of the name of the described entities.
559 uint64_t getStringOffset() const { return StringOffset; }
560
561 /// Return the string referenced by this name table entry or nullptr if the
562 /// string offset is not valid.
563 const char *getString() const {
564 uint64_t Off = StringOffset;
565 return StrData.getCStr(OffsetPtr: &Off);
566 }
567
568 /// Compares the name of this entry against Target, returning true if they
569 /// are equal. This is more efficient in hot code paths that do not need the
570 /// length of the name.
571 bool sameNameAs(StringRef Target) const {
572 // Note: this is not the name, but the rest of debug_str starting from
573 // name. This handles corrupt data (non-null terminated) without
574 // overrunning the buffer.
575 StringRef Data = StrData.getData().substr(Start: StringOffset);
576 size_t TargetSize = Target.size();
577 return Data.size() > TargetSize && !Data[TargetSize] &&
578 strncmp(s1: Data.data(), s2: Target.data(), n: TargetSize) == 0;
579 }
580
581 /// Returns the offset of the first Entry in the list.
582 uint64_t getEntryOffset() const { return EntryOffset; }
583 };
584
585 /// Offsets for the start of various important tables from the start of the
586 /// section.
587 struct DWARFDebugNamesOffsets {
588 uint64_t CUsBase;
589 uint64_t BucketsBase;
590 uint64_t HashesBase;
591 uint64_t StringOffsetsBase;
592 uint64_t EntryOffsetsBase;
593 uint64_t EntriesBase;
594 };
595
596 /// Represents a single accelerator table within the DWARF v5 .debug_names
597 /// section.
598 class NameIndex {
599 DenseSet<Abbrev, AbbrevMapInfo> Abbrevs;
600 struct Header Hdr;
601 const DWARFDebugNames &Section;
602
603 // Base of the whole unit and of various important tables, as offsets from
604 // the start of the section.
605 uint64_t Base;
606 DWARFDebugNamesOffsets Offsets;
607
608 void dumpCUs(ScopedPrinter &W) const;
609 void dumpLocalTUs(ScopedPrinter &W) const;
610 void dumpForeignTUs(ScopedPrinter &W) const;
611 void dumpAbbreviations(ScopedPrinter &W) const;
612 bool dumpEntry(ScopedPrinter &W, uint64_t *Offset) const;
613 void dumpName(ScopedPrinter &W, const NameTableEntry &NTE,
614 std::optional<uint32_t> Hash) const;
615 void dumpBucket(ScopedPrinter &W, uint32_t Bucket) const;
616
617 Expected<AttributeEncoding> extractAttributeEncoding(uint64_t *Offset);
618
619 Expected<std::vector<AttributeEncoding>>
620 extractAttributeEncodings(uint64_t *Offset);
621
622 Expected<Abbrev> extractAbbrev(uint64_t *Offset);
623
624 public:
625 NameIndex(const DWARFDebugNames &Section, uint64_t Base)
626 : Section(Section), Base(Base) {}
627
628 /// Returns Hdr field
629 Header getHeader() const { return Hdr; }
630
631 /// Returns Offsets field
632 DWARFDebugNamesOffsets getOffsets() const { return Offsets; }
633
634 /// Reads offset of compilation unit CU. CU is 0-based.
635 uint64_t getCUOffset(uint32_t CU) const;
636 uint32_t getCUCount() const { return Hdr.CompUnitCount; }
637
638 /// Reads offset of local type unit TU, TU is 0-based.
639 uint64_t getLocalTUOffset(uint32_t TU) const;
640 uint32_t getLocalTUCount() const { return Hdr.LocalTypeUnitCount; }
641
642 /// Reads signature of foreign type unit TU. TU is 0-based.
643 uint64_t getForeignTUSignature(uint32_t TU) const;
644 uint32_t getForeignTUCount() const { return Hdr.ForeignTypeUnitCount; }
645
646 /// Reads an entry in the Bucket Array for the given Bucket. The returned
647 /// value is a (1-based) index into the Names, StringOffsets and
648 /// EntryOffsets arrays. The input Bucket index is 0-based.
649 uint32_t getBucketArrayEntry(uint32_t Bucket) const;
650 uint32_t getBucketCount() const { return Hdr.BucketCount; }
651
652 /// Reads an entry in the Hash Array for the given Index. The input Index
653 /// is 1-based.
654 uint32_t getHashArrayEntry(uint32_t Index) const;
655
656 /// Reads an entry in the Name Table for the given Index. The Name Table
657 /// consists of two arrays -- String Offsets and Entry Offsets. The returned
658 /// offsets are relative to the starts of respective sections. Input Index
659 /// is 1-based.
660 NameTableEntry getNameTableEntry(uint32_t Index) const;
661
662 uint32_t getNameCount() const { return Hdr.NameCount; }
663
664 const DenseSet<Abbrev, AbbrevMapInfo> &getAbbrevs() const {
665 return Abbrevs;
666 }
667
668 Expected<Entry> getEntry(uint64_t *Offset) const;
669
670 /// Returns the Entry at the relative `Offset` from the start of the Entry
671 /// pool.
672 Expected<Entry> getEntryAtRelativeOffset(uint64_t Offset) const {
673 auto OffsetFromSection = Offset + this->Offsets.EntriesBase;
674 return getEntry(Offset: &OffsetFromSection);
675 }
676
677 /// Look up all entries in this Name Index matching \c Key.
678 iterator_range<ValueIterator> equal_range(StringRef Key) const;
679
680 NameIterator begin() const { return NameIterator(this, 1); }
681 NameIterator end() const { return NameIterator(this, getNameCount() + 1); }
682
683 Error extract();
684 uint64_t getUnitOffset() const { return Base; }
685 uint64_t getNextUnitOffset() const {
686 return Base + dwarf::getUnitLengthFieldByteSize(Format: Hdr.Format) +
687 Hdr.UnitLength;
688 }
689 void dump(ScopedPrinter &W) const;
690
691 friend class DWARFDebugNames;
692 };
693
694 class ValueIterator {
695 public:
696 using iterator_category = std::input_iterator_tag;
697 using value_type = Entry;
698 using difference_type = std::ptrdiff_t;
699 using pointer = value_type *;
700 using reference = value_type &;
701
702 private:
703 /// The Name Index we are currently iterating through. The implementation
704 /// relies on the fact that this can also be used as an iterator into the
705 /// "NameIndices" vector in the Accelerator section.
706 const NameIndex *CurrentIndex = nullptr;
707
708 /// Whether this is a local iterator (searches in CurrentIndex only) or not
709 /// (searches all name indices).
710 bool IsLocal;
711
712 std::optional<Entry> CurrentEntry;
713 uint64_t DataOffset = 0; ///< Offset into the section.
714 std::string Key; ///< The Key we are searching for.
715 std::optional<uint32_t> Hash; ///< Hash of Key, if it has been computed.
716
717 bool getEntryAtCurrentOffset();
718 std::optional<uint64_t> findEntryOffsetInCurrentIndex();
719 bool findInCurrentIndex();
720 void searchFromStartOfCurrentIndex();
721 void next();
722
723 /// Set the iterator to the "end" state.
724 void setEnd() { *this = ValueIterator(); }
725
726 public:
727 /// Create a "begin" iterator for looping over all entries in the
728 /// accelerator table matching Key. The iterator will run through all Name
729 /// Indexes in the section in sequence.
730 ValueIterator(const DWARFDebugNames &AccelTable, StringRef Key);
731
732 /// Create a "begin" iterator for looping over all entries in a specific
733 /// Name Index. Other indices in the section will not be visited.
734 ValueIterator(const NameIndex &NI, StringRef Key);
735
736 /// End marker.
737 ValueIterator() = default;
738
739 const Entry &operator*() const { return *CurrentEntry; }
740 ValueIterator &operator++() {
741 next();
742 return *this;
743 }
744 ValueIterator operator++(int) {
745 ValueIterator I = *this;
746 next();
747 return I;
748 }
749
750 friend bool operator==(const ValueIterator &A, const ValueIterator &B) {
751 return A.CurrentIndex == B.CurrentIndex && A.DataOffset == B.DataOffset;
752 }
753 friend bool operator!=(const ValueIterator &A, const ValueIterator &B) {
754 return !(A == B);
755 }
756 };
757
758 class NameIterator {
759
760 /// The Name Index we are iterating through.
761 const NameIndex *CurrentIndex;
762
763 /// The current name in the Name Index.
764 uint32_t CurrentName;
765
766 void next() {
767 assert(CurrentName <= CurrentIndex->getNameCount());
768 ++CurrentName;
769 }
770
771 public:
772 using iterator_category = std::input_iterator_tag;
773 using value_type = NameTableEntry;
774 using difference_type = uint32_t;
775 using pointer = NameTableEntry *;
776 using reference = NameTableEntry; // We return entries by value.
777
778 /// Creates an iterator whose initial position is name CurrentName in
779 /// CurrentIndex.
780 NameIterator(const NameIndex *CurrentIndex, uint32_t CurrentName)
781 : CurrentIndex(CurrentIndex), CurrentName(CurrentName) {}
782
783 NameTableEntry operator*() const {
784 return CurrentIndex->getNameTableEntry(Index: CurrentName);
785 }
786 NameIterator &operator++() {
787 next();
788 return *this;
789 }
790 NameIterator operator++(int) {
791 NameIterator I = *this;
792 next();
793 return I;
794 }
795
796 friend bool operator==(const NameIterator &A, const NameIterator &B) {
797 return A.CurrentIndex == B.CurrentIndex && A.CurrentName == B.CurrentName;
798 }
799 friend bool operator!=(const NameIterator &A, const NameIterator &B) {
800 return !(A == B);
801 }
802 };
803
804private:
805 SmallVector<NameIndex, 0> NameIndices;
806 DenseMap<uint64_t, const NameIndex *> CUToNameIndex;
807
808public:
809 DWARFDebugNames(const DWARFDataExtractor &AccelSection,
810 DataExtractor StringSection)
811 : DWARFAcceleratorTable(AccelSection, StringSection) {}
812
813 Error extract() override;
814 void dump(raw_ostream &OS) const override;
815
816 /// Look up all entries in the accelerator table matching \c Key.
817 iterator_range<ValueIterator> equal_range(StringRef Key) const;
818
819 using const_iterator = SmallVector<NameIndex, 0>::const_iterator;
820 const_iterator begin() const { return NameIndices.begin(); }
821 const_iterator end() const { return NameIndices.end(); }
822
823 /// Return the Name Index covering the compile unit at CUOffset, or nullptr if
824 /// there is no Name Index covering that unit.
825 const NameIndex *getCUNameIndex(uint64_t CUOffset);
826};
827
828/// Calculates the starting offsets for various sections within the
829/// .debug_names section.
830namespace dwarf {
831DWARFDebugNames::DWARFDebugNamesOffsets
832findDebugNamesOffsets(uint64_t EndOfHeaderOffset,
833 const DWARFDebugNames::Header &Hdr);
834}
835
836/// If `Name` is the name of a templated function that includes template
837/// parameters, returns a substring of `Name` containing no template
838/// parameters.
839/// E.g.: StripTemplateParameters("foo<int>") = "foo".
840std::optional<StringRef> StripTemplateParameters(StringRef Name);
841
842struct ObjCSelectorNames {
843 /// For "-[A(Category) method:]", this would be "method:"
844 StringRef Selector;
845 /// For "-[A(Category) method:]", this would be "A(category)"
846 StringRef ClassName;
847 /// For "-[A(Category) method:]", this would be "A"
848 std::optional<StringRef> ClassNameNoCategory;
849 /// For "-[A(Category) method:]", this would be "A method:"
850 std::optional<std::string> MethodNameNoCategory;
851};
852
853/// If `Name` is the AT_name of a DIE which refers to an Objective-C selector,
854/// returns an instance of ObjCSelectorNames. The Selector and ClassName fields
855/// are guaranteed to be non-empty in the result.
856std::optional<ObjCSelectorNames> getObjCNamesIfSelector(StringRef Name);
857
858} // end namespace llvm
859
860#endif // LLVM_DEBUGINFO_DWARF_DWARFACCELERATORTABLE_H
861