DWARFAcceleratorTable: Add an iterator-based api for accessing names in the index

[labath]

Summary

Back when we were introducing the DWARF v5 name index, there was a
short discussion whether we shouldn't have a nicer api for iterating
over the index. At that time, I did not find it necessary since the
iteration over names was done only from within the index itself (and I
figured the internal implementation can deal with a slightly rough
interface).

However, now I ran into a use for this kind of API in LLDB (for finding
all names matching a regular expression), so it looked like a nice
opportunity to introduce one. To make the API more useful, I've made the
NameTableEntry class a bit smarter: it now stores the string section
reference (so it can return its name) and its position in the name index
(mainly useful for dumping/logging).

I also convert the internal users to use the new API, which should also
give test coverage for the added code.

[JDevlieghere]

Look fine to me

include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h

376

Have you considered wrapping this in a StringRef?

535

CurrentName being an int feels weird, but it's consistent with the other iterator and I don't have a better suggestion.

[labath]

include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h

376

Yes. My reasoning for not doing that is that it allows you to distinguish between the "string not found" and "empty string" cases. Though I could be easily convinced to add a StringRef version for users which don't care about the distinction.

include/llvm/DebugInfo/DWARF/DWARFAcceleratorTable.h

struct HeaderPOD {
     uint32_t BucketCount;
     uint32_t NameCount;
     uint32_t AbbrevTableSize;
     uint32_t AugmentationStringSize;
   };
 
 public:
   class NameIndex;
+  class NameIterator;
   class ValueIterator;
 
   /// Dwarf 5 Name Index header.
   struct Header : public HeaderPOD {
     SmallString<8> AugmentationString;
 
     Error extract(const DWARFDataExtractor &AS, uint32_t *Offset);
     void dump(ScopedPrinter &W) const;
struct AbbrevMapInfo {
     static bool isEqual(const Abbrev &LHS, const Abbrev &RHS) {
       return LHS.Code == RHS.Code;
     }
   };
 
 public:
   /// A single entry in the Name Table (Dwarf 5 sect. 6.1.1.4.6) of the Name
   /// Index.
-  struct NameTableEntry {
-    uint32_t StringOffset; ///< Offset of the name of the described entities.
-    uint32_t EntryOffset;  ///< Offset of the first Entry in the list.
+  class NameTableEntry {
+    DataExtractor StrData;
+
+    uint32_t Index;
+    uint32_t StringOffset;
+    uint32_t EntryOffset;
+
+  public:
+    NameTableEntry(const DataExtractor &StrData, uint32_t Index,
+                   uint32_t StringOffset, uint32_t EntryOffset)
+        : StrData(StrData), Index(Index), StringOffset(StringOffset),
+          EntryOffset(EntryOffset) {}
+
+    /// Return the index of this name in the parent Name Index.
+    uint32_t getIndex() const { return Index; }
+
+    /// Returns the offset of the name of the described entities.
+    uint32_t getStringOffset() const { return StringOffset; }
+
+    /// Return the string referenced by this name table entry or nullptr if the
+    /// string offset is not valid.
+    const char *getString() const {
+      uint32_t Off = StringOffset;
+      return StrData.getCStr(&Off);
+    }
+
+    /// Returns the offset of the first Entry in the list.
+    uint32_t getEntryOffset() const { return EntryOffset; }
   };
 
   /// Represents a single accelerator table within the Dwarf 5 .debug_names
   /// section.
   class NameIndex {
     DenseSet<Abbrev, AbbrevMapInfo> Abbrevs;
     struct Header Hdr;
     const DWARFDebugNames &Section;
 
     // Base of the whole unit and of various important tables, as offsets from
     // the start of the section.
     uint32_t Base;
     uint32_t CUsBase;
     uint32_t BucketsBase;
     uint32_t HashesBase;
     uint32_t StringOffsetsBase;
     uint32_t EntryOffsetsBase;
     uint32_t EntriesBase;
 
     void dumpCUs(ScopedPrinter &W) const;
     void dumpLocalTUs(ScopedPrinter &W) const;
     void dumpForeignTUs(ScopedPrinter &W) const;
     void dumpAbbreviations(ScopedPrinter &W) const;
     bool dumpEntry(ScopedPrinter &W, uint32_t *Offset) const;
-    void dumpName(ScopedPrinter &W, uint32_t Index,
+    void dumpName(ScopedPrinter &W, const NameTableEntry &NTE,
                   Optional<uint32_t> Hash) const;
     void dumpBucket(ScopedPrinter &W, uint32_t Bucket) const;
 
     Expected<AttributeEncoding> extractAttributeEncoding(uint32_t *Offset);
 
     Expected<std::vector<AttributeEncoding>>
     extractAttributeEncodings(uint32_t *Offset);
 
const DenseSet<Abbrev, AbbrevMapInfo> &getAbbrevs() const {
       return Abbrevs;
     }
 
     Expected<Entry> getEntry(uint32_t *Offset) const;
 
     /// Look up all entries in this Name Index matching \c Key.
     iterator_range<ValueIterator> equal_range(StringRef Key) const;
 
+    NameIterator begin() const { return NameIterator(this, 1); }
+    NameIterator end() const { return NameIterator(this, getNameCount() + 1); }
+
     llvm::Error extract();
     uint32_t getUnitOffset() const { return Base; }
     uint32_t getNextUnitOffset() const { return Base + 4 + Hdr.UnitLength; }
     void dump(ScopedPrinter &W) const;
 
     friend class DWARFDebugNames;
   };
 
public:
     friend bool operator==(const ValueIterator &A, const ValueIterator &B) {
       return A.CurrentIndex == B.CurrentIndex && A.DataOffset == B.DataOffset;
     }
     friend bool operator!=(const ValueIterator &A, const ValueIterator &B) {
       return !(A == B);
     }
   };
 
+  class NameIterator {
+
+    /// The Name Index we are iterating through.
+    const NameIndex *CurrentIndex;
+
+    /// The current name in the Name Index.
+    uint32_t CurrentName;
+
+    void next() {
+      assert(CurrentName <= CurrentIndex->getNameCount());
+      ++CurrentName;
+    }
+
+  public:
+    using iterator_category = std::input_iterator_tag;
+    using value_type = NameTableEntry;
+    using difference_type = uint32_t;
+    using pointer = NameTableEntry *;
+    using reference = NameTableEntry; // We return entries by value.
+
+    /// Creates an iterator whose initial position is name CurrentName in
+    /// CurrentIndex.
+    NameIterator(const NameIndex *CurrentIndex, uint32_t CurrentName)
+        : CurrentIndex(CurrentIndex), CurrentName(CurrentName) {}
+
+    NameTableEntry operator*() const {
+      return CurrentIndex->getNameTableEntry(CurrentName);
+    }
+    NameIterator &operator++() {
+      next();
+      return *this;
+    }
+    NameIterator operator++(int) {
+      NameIterator I = *this;
+      next();
+      return I;
+    }
+
+    friend bool operator==(const NameIterator &A, const NameIterator &B) {
+      return A.CurrentIndex == B.CurrentIndex && A.CurrentName == B.CurrentName;
+    }
+    friend bool operator!=(const NameIterator &A, const NameIterator &B) {
+      return !(A == B);
+    }
+  };
+
 private:
   SmallVector<NameIndex, 0> NameIndices;
   DenseMap<uint32_t, const NameIndex *> CUToNameIndex;
 
 public:
   DWARFDebugNames(const DWARFDataExtractor &AccelSection,
                   DataExtractor StringSection)
       : DWARFAcceleratorTable(AccelSection, StringSection) {}

include/llvm/DebugInfo/DWARF/DWARFVerifier.h

private:
   unsigned verifyDebugNamesCULists(const DWARFDebugNames &AccelTable);
   unsigned verifyNameIndexBuckets(const DWARFDebugNames::NameIndex &NI,
                                   const DataExtractor &StrData);
   unsigned verifyNameIndexAbbrevs(const DWARFDebugNames::NameIndex &NI);
   unsigned verifyNameIndexAttribute(const DWARFDebugNames::NameIndex &NI,
                                     const DWARFDebugNames::Abbrev &Abbr,
                                     DWARFDebugNames::AttributeEncoding AttrEnc);
   unsigned verifyNameIndexEntries(const DWARFDebugNames::NameIndex &NI,
-                                  uint32_t Name, const DataExtractor &StrData);
+                                  const DWARFDebugNames::NameTableEntry &NTE);
   unsigned verifyNameIndexCompleteness(const DWARFDie &Die,
                                        const DWARFDebugNames::NameIndex &NI);
 
   /// Verify that the DWARF v5 accelerator table is valid.
   ///
   /// This function currently checks that:
   /// - Headers individual Name Indices fit into the section and can be parsed.
   /// - Abbreviation tables can be parsed and contain valid index attributes

lib/DebugInfo/DWARF/DWARFAcceleratorTable.cpp

DWARFDebugNames::NameIndex::getNameTableEntry(uint32_t Index) const {
   assert(0 < Index && Index <= Hdr.NameCount);
   uint32_t StringOffsetOffset = StringOffsetsBase + 4 * (Index - 1);
   uint32_t EntryOffsetOffset = EntryOffsetsBase + 4 * (Index - 1);
   const DWARFDataExtractor &AS = Section.AccelSection;
 
   uint32_t StringOffset = AS.getRelocatedValue(4, &StringOffsetOffset);
   uint32_t EntryOffset = AS.getU32(&EntryOffsetOffset);
   EntryOffset += EntriesBase;
-  return {StringOffset, EntryOffset};
+  return {Section.StringSection, Index, StringOffset, EntryOffset};
 }
 
 uint32_t
 DWARFDebugNames::NameIndex::getBucketArrayEntry(uint32_t Bucket) const {
   assert(Bucket < Hdr.BucketCount);
   uint32_t BucketOffset = BucketsBase + 4 * Bucket;
   return Section.AccelSection.getU32(&BucketOffset);
 }
if (!EntryOr) {
     return false;
   }
 
   DictScope EntryScope(W, ("Entry @ 0x" + Twine::utohexstr(EntryId)).str());
   EntryOr->dump(W);
   return true;
 }
 
-void DWARFDebugNames::NameIndex::dumpName(ScopedPrinter &W, uint32_t Index,
+void DWARFDebugNames::NameIndex::dumpName(ScopedPrinter &W,
+                                          const NameTableEntry &NTE,
                                           Optional<uint32_t> Hash) const {
-  const DataExtractor &SS = Section.StringSection;
-  NameTableEntry NTE = getNameTableEntry(Index);
-
-  DictScope NameScope(W, ("Name " + Twine(Index)).str());
+  DictScope NameScope(W, ("Name " + Twine(NTE.getIndex())).str());
   if (Hash)
     W.printHex("Hash", *Hash);
 
-  W.startLine() << format("String: 0x%08x", NTE.StringOffset);
-  W.getOStream() << " \"" << SS.getCStr(&NTE.StringOffset) << "\"\n";
+  W.startLine() << format("String: 0x%08x", NTE.getStringOffset());
+  W.getOStream() << " \"" << NTE.getString() << "\"\n";
 
-  while (dumpEntry(W, &NTE.EntryOffset))
+  uint32_t EntryOffset = NTE.getEntryOffset();
+  while (dumpEntry(W, &EntryOffset))
     /*empty*/;
 }
 
 void DWARFDebugNames::NameIndex::dumpCUs(ScopedPrinter &W) const {
   ListScope CUScope(W, "Compilation Unit offsets");
   for (uint32_t CU = 0; CU < Hdr.CompUnitCount; ++CU)
     W.startLine() << format("CU[%u]: 0x%08x\n", CU, getCUOffset(CU));
 }
if (Index > Hdr.NameCount) {
     return;
   }
 
   for (; Index <= Hdr.NameCount; ++Index) {
     uint32_t Hash = getHashArrayEntry(Index);
     if (Hash % Hdr.BucketCount != Bucket)
       break;
 
-    dumpName(W, Index, Hash);
+    dumpName(W, getNameTableEntry(Index), Hash);
   }
 }
 
 LLVM_DUMP_METHOD void DWARFDebugNames::NameIndex::dump(ScopedPrinter &W) const {
   DictScope UnitScope(W, ("Name Index @ 0x" + Twine::utohexstr(Base)).str());
   Hdr.dump(W);
   dumpCUs(W);
   dumpLocalTUs(W);
   dumpForeignTUs(W);
   dumpAbbreviations(W);
 
   if (Hdr.BucketCount > 0) {
     for (uint32_t Bucket = 0; Bucket < Hdr.BucketCount; ++Bucket)
       dumpBucket(W, Bucket);
     return;
   }
 
   W.startLine() << "Hash table not present\n";
-  for (uint32_t Index = 1; Index <= Hdr.NameCount; ++Index)
-    dumpName(W, Index, None);
+  for (NameTableEntry NTE : *this)
+    dumpName(W, NTE, None);
 }
 
 llvm::Error DWARFDebugNames::extract() {
   uint32_t Offset = 0;
   while (AccelSection.isValidOffset(Offset)) {
     NameIndex Next(*this, Offset);
     if (llvm::Error E = Next.extract())
       return E;
for (const NameIndex &NI : NameIndices)
     NI.dump(W);
 }
 
 Optional<uint32_t>
 DWARFDebugNames::ValueIterator::findEntryOffsetInCurrentIndex() {
   const Header &Hdr = CurrentIndex->Hdr;
   if (Hdr.BucketCount == 0) {
     // No Hash Table, We need to search through all names in the Name Index.
-    for (uint32_t Index = 1; Index <= Hdr.NameCount; ++Index) {
-      NameTableEntry NTE = CurrentIndex->getNameTableEntry(Index);
-      if (CurrentIndex->Section.StringSection.getCStr(&NTE.StringOffset) == Key)
-        return NTE.EntryOffset;
+    for (NameTableEntry NTE : *CurrentIndex) {
+      if (NTE.getString() == Key)
+        return NTE.getEntryOffset();
     }
     return None;
   }
 
   // The Name Index has a Hash Table, so use that to speed up the search.
   // Compute the Key Hash, if it has not been done already.
   if (!Hash)
     Hash = caseFoldingDjbHash(Key);
   uint32_t Bucket = *Hash % Hdr.BucketCount;
   uint32_t Index = CurrentIndex->getBucketArrayEntry(Bucket);
   if (Index == 0)
     return None; // Empty bucket
 
   for (; Index <= Hdr.NameCount; ++Index) {
     uint32_t Hash = CurrentIndex->getHashArrayEntry(Index);
     if (Hash % Hdr.BucketCount != Bucket)
       return None; // End of bucket
 
     NameTableEntry NTE = CurrentIndex->getNameTableEntry(Index);
-    if (CurrentIndex->Section.StringSection.getCStr(&NTE.StringOffset) == Key)
-      return NTE.EntryOffset;
+    if (NTE.getString() == Key)
+      return NTE.getEntryOffset();
   }
   return None;
 }
 
 bool DWARFDebugNames::ValueIterator::getEntryAtCurrentOffset() {
   auto EntryOr = CurrentIndex->getEntry(&DataOffset);
   if (!EntryOr) {
     consumeError(EntryOr.takeError());

lib/DebugInfo/DWARF/DWARFVerifier.cpp

for (const BucketInfo &B : BucketStarts) {
     // This find the end of this bucket and also verifies that all the hashes in
     // this bucket are correct by comparing the stored hashes to the ones we
     // compute ourselves.
     while (Idx <= NI.getNameCount()) {
       uint32_t Hash = NI.getHashArrayEntry(Idx);
       if (Hash % NI.getBucketCount() != B.Bucket)
         break;
 
-      auto NTE = NI.getNameTableEntry(Idx);
-      const char *Str = StrData.getCStr(&NTE.StringOffset);
+      const char *Str = NI.getNameTableEntry(Idx).getString();
       if (caseFoldingDjbHash(Str) != Hash) {
         error() << formatv("Name Index @ {0:x}: String ({1}) at index {2} "
                            "hashes to {3:x}, but "
                            "the Name Index hash is {4:x}\n",
                            NI.getUnitOffset(), Str, Idx,
                            caseFoldingDjbHash(Str), Hash);
         ++NumErrors;
       }
static SmallVector<StringRef, 2> getNames(const DWARFDie &DIE) {
   if (const char *Str = DIE.getName(DINameKind::LinkageName)) {
     if (Result.empty() || Result[0] != Str)
       Result.emplace_back(Str);
   }
 
   return Result;
 }
 
-unsigned
-DWARFVerifier::verifyNameIndexEntries(const DWARFDebugNames::NameIndex &NI,
-                                      uint32_t Name,
-                                      const DataExtractor &StrData) {
+unsigned DWARFVerifier::verifyNameIndexEntries(
+    const DWARFDebugNames::NameIndex &NI,
+    const DWARFDebugNames::NameTableEntry &NTE) {
   // Verifying type unit indexes not supported.
   if (NI.getLocalTUCount() + NI.getForeignTUCount() > 0)
     return 0;
 
-  DWARFDebugNames::NameTableEntry NTE = NI.getNameTableEntry(Name);
-  const char *CStr = StrData.getCStr(&NTE.StringOffset);
+  const char *CStr = NTE.getString();
   if (!CStr) {
     error() << formatv(
         "Name Index @ {0:x}: Unable to get string associated with name {1}.\n",
-        NI.getUnitOffset(), Name);
+        NI.getUnitOffset(), NTE.getIndex());
     return 1;
   }
   StringRef Str(CStr);
 
   unsigned NumErrors = 0;
   unsigned NumEntries = 0;
-  uint32_t EntryID = NTE.EntryOffset;
-  Expected<DWARFDebugNames::Entry> EntryOr = NI.getEntry(&NTE.EntryOffset);
-  for (; EntryOr; ++NumEntries, EntryID = NTE.EntryOffset,
-                                EntryOr = NI.getEntry(&NTE.EntryOffset)) {
+  uint32_t EntryID = NTE.getEntryOffset();
+  uint32_t NextEntryID = EntryID;
+  Expected<DWARFDebugNames::Entry> EntryOr = NI.getEntry(&NextEntryID);
+  for (; EntryOr; ++NumEntries, EntryID = NextEntryID,
+                                EntryOr = NI.getEntry(&NextEntryID)) {
     uint32_t CUIndex = *EntryOr->getCUIndex();
     if (CUIndex > NI.getCUCount()) {
       error() << formatv("Name Index @ {0:x}: Entry @ {1:x} contains an "
                          "invalid CU index ({2}).\n",
                          NI.getUnitOffset(), EntryID, CUIndex);
       ++NumErrors;
       continue;
     }
for (; EntryOr; ++NumEntries, EntryID = NextEntryID,
     }
   }
   handleAllErrors(EntryOr.takeError(),
                   [&](const DWARFDebugNames::SentinelError &) {
                     if (NumEntries > 0)
                       return;
                     error() << formatv("Name Index @ {0:x}: Name {1} ({2}) is "
                                        "not associated with any entries.\n",
-                                       NI.getUnitOffset(), Name, Str);
+                                       NI.getUnitOffset(), NTE.getIndex(), Str);
                     ++NumErrors;
                   },
                   [&](const ErrorInfoBase &Info) {
-                    error() << formatv(
-                        "Name Index @ {0:x}: Name {1} ({2}): {3}\n",
-                        NI.getUnitOffset(), Name, Str, Info.message());
+                    error()
+                        << formatv("Name Index @ {0:x}: Name {1} ({2}): {3}\n",
+                                   NI.getUnitOffset(), NTE.getIndex(), Str,
+                                   Info.message());
                     ++NumErrors;
                   });
   return NumErrors;
 }
 
 static bool isVariableIndexable(const DWARFDie &Die, DWARFContext &DCtx) {
   Optional<DWARFFormValue> Location = Die.findRecursively(DW_AT_location);
   if (!Location)
for (const auto &NI : AccelTable)
     NumErrors += verifyNameIndexBuckets(NI, StrData);
   for (const auto &NI : AccelTable)
     NumErrors += verifyNameIndexAbbrevs(NI);
 
   // Don't attempt Entry validation if any of the previous checks found errors
   if (NumErrors > 0)
     return NumErrors;
   for (const auto &NI : AccelTable)
-    for (uint64_t Name = 1; Name <= NI.getNameCount(); ++Name)
-      NumErrors += verifyNameIndexEntries(NI, Name, StrData);
+    for (DWARFDebugNames::NameTableEntry NTE : NI)
+      NumErrors += verifyNameIndexEntries(NI, NTE);
 
   if (NumErrors > 0)
     return NumErrors;
 
   for (const std::unique_ptr<DWARFCompileUnit> &CU : DCtx.compile_units()) {
     if (const DWARFDebugNames::NameIndex *NI =
             AccelTable.getCUNameIndex(CU->getOffset())) {
       for (const DWARFDebugInfoEntry &Die : CU->dies())