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