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